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 (≤) 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

思路：
　　先找到根节点，数字r未出现，则r为根节点，因为根节点不是任何节点的子节点
　　然后静态构造树
　　再调用平常的层序遍历和中序遍历
　　所谓的二叉树反转，就是原来先读左子树，再读右子树
　　现在改为先读右子树，再读左子树

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 struct Node
 6 {
 7     int l, r;
 8 };
 9 int N, root[15] = { 0 };
10 Node tree[15];
11 vector<int>lev, in;
12 void levelOrde(int t)
13 {
14     if (t == -1)
15         return;
16     queue<int>q;
17     q.push(t);
18     while (!q.empty())
19     {
20         t = q.front();
21         q.pop();
22         lev.push_back(t);
23         if (tree[t].r != -1)//先进右
24             q.push(tree[t].r);
25         if (tree[t].l != -1)
26             q.push(tree[t].l);
27     }
28 }
29 void inOrder(int t)
30 {
31     if (t == -1)
32         return;
33     inOrder(tree[t].r);
34     in.push_back(t);
35     inOrder(tree[t].l);
36 }
37 int main()
38 {
39     cin >> N;
40     char l, r;
41     for (int i = 0; i < N; ++i)
42     {
43         cin >> l >> r;
44         if (l != '-')
45         {
46             tree[i].l = l - '0';
47             root[l - '0'] = -1;//去除为根的可能性
48         }
49         else
50             tree[i].l = -1;
51         if (r != '-')
52         {
53             tree[i].r = r - '0';
54             root[r - '0'] = -1;//去除为根的可能性
55         }
56         else
57             tree[i].r = -1;
58     }
59     for (int i = 0; i < N; ++i)
60     {
61         if (root[i] == 0)
62         {
63             r = i;
64             break;//找到了根节点
65         }
66     }
67     levelOrde(r);
68     inOrder(r);
69     for (int i = 0; i < N; ++i)
70         cout << lev[i] << (i == N - 1 ? "" : " ");
71     cout << endl;
72     for (int i = 0; i < N; ++i)
73         cout << in[i] << (i == N - 1 ? "" : " ");
74     return 0;
75 }