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:

81 -- -0 -2 7- -- -5 -4 6

Sample Output:

3 7 2 6 4 0 5 16 5 7 4 3 2 0 1 代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;struct tree{ int l,r;}s[10];int n,v[10],head,flag = 0;char a,b;void invert(int head){ if(head == -1)return; invert(s[head].l); invert(s[head].r); swap(s[head].l,s[head].r);}void in_order(int head){ if(head == -1)return; in_order(s[head].l); if(flag)printf(" %d",head); else printf("%d",head); flag ++; in_order(s[head].r);}void level_order(int head){ int q[10],he = 0,ta = 0; if(head == -1)return ; q[ta ++] = head; while(he < ta) { int i = q[he]; if(s[i].l != -1)q[ta ++] = s[i].l; if(s[i].r != -1)q[ta ++] = s[i].r; if(he)cout<<' '<
             
              >n; for(int i = 0;i < n;i ++) { cin>>a>>b; if(a != '-')s[i].l = a - '0',v[s[i].l] = 1; else s[i].l = -1; if(b != '-')s[i].r = b - '0',v[s[i].r] = 1; else s[i].r = -1; } for(int i = 0;i < n;i ++) if(!v[i]) { head = i; break; } invert(head); level_order(head); in_order(head);}