1102. Invert a Binary Tree (25)

拼搏现实的明天。 2022-05-30 06:09 184阅读 0赞

The following is from Max Howell @twitter:

*Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so fuck off.*

Now it's your turn to prove that YOU CAN invert a binary tree!

**Input Specification:**

Each input file contains one test case. For each case, the first line gives a positive integer N (<=10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node from 0 to N-1, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

**Output Specification:**

For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

**Sample Input:**

8
    1 -
    - -
    0 -
    2 7
    - -
    - -
    5 -
    4 6

**Sample Output:**

3 7 2 6 4 0 5 1
    6 5 7 4 3 2 0 1

--------------------

题目大意：

代码：

#include<stdio.h>
    #include<queue>
    using namespace std;
    struct node
    {
    	int flag;
    	int lchild,rchild;
    }tree[20];
    int flag=0;
    void inorder(int root)
    {
    	//printf("%d\n",root);
    	if(root!=-1)
    	{
    		inorder(tree[root].rchild);
    		if(flag==0)
    		{
    			printf("%d",root);
    			flag=1;
    		}
    		else
    		{
    			printf(" %d",root);
    		}
    		inorder(tree[root].lchild);
    	}
    }
    int tag=0;
    void levelorder(int root)
    {
    	queue<int> q;
    	q.push(root);
    	while(!q.empty())
    	{
    		int tmp=q.front();
    		q.pop();
    		if(tmp!=-1)
    		{
    			q.push(tree[tmp].rchild);
    			q.push(tree[tmp].lchild);
    		    if(tag==0)
    			{
    			   printf("%d",tmp);
    			   tag=1;
    			}
    		    else
    			{
    			   printf(" %d",tmp);
    			}
    		}
    	}
    }
    int main()
    {
    	int i,j,n,m,k,t;
    	char l[2],r[2];
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%s %s",l,r);
    		if(l[0]!='-')
    		{
    			tree[i].lchild=l[0]-'0';
    		    tree[l[0]-'0'].flag=1;
    		}
    		else
    		{
    			tree[i].lchild=-1;
    		}
    		if(r[0]!='-')
    		{
    			tree[i].rchild=r[0]-'0';
    		    tree[r[0]-'0'].flag=1;
    		}
    		else
    		{
    			tree[i].rchild=-1;
    		}
    	}
    	for(i=0;i<n;i++)
    	{
    		if(tree[i].flag==0)
    		{
    			k=i;
    			break;
    		}
    	}
    	//printf("%d\n",k);
    	levelorder(k);
    	printf("\n");
    	inorder(k);
    	printf("\n");
    return 0;
    }