PAT-A-1102 Invert a Binary Tree (25)

题目

题目链接 反转二叉树 ## description 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. ## 题目描述 现在轮到你来证明你可以反转一棵二叉树了! ## 输入 每个输入文件包括一个测试用例,第一行给出一个正整数N(<=10),他是树中节点的总数。节点从0~N-1编号。

接下来是N行,每行对应一个从0到N-1的节点,并给出节点的左右子节点的索引,如果孩子不存在,就在该位置放置'-'。两个孩子之间由空格隔开。 ## 输出 对于每个测试用例,在一行中输出层次遍历,然后在第二行中,输出这棵树的反转的层次遍历,数字之间由空格隔开,并且行的末尾不得有额外的空格。 # 解题 ## 思路分析 1. 找到这棵树的根。 2. 层次遍历没啥好说的,使用queue队列,一层层的遍历就好了。 3. 对于反向的中序遍历,遍历顺序是“右左根”。递归去写即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<vector>
#include<queue>
#pragma warning(disable:4996)
using namespace std;

typedef struct
{
int lchild=-1, rchild=-1;
}node;
vector<node> T;
vector<bool> FindRoot;
int N;
char temp1, temp2;
bool flag = false;
void InOrder(int root)
{
if (T[root].rchild != -1)
InOrder(T[root].rchild);
if (flag)
cout << ' ';
cout << root;
flag = true;
if (T[root].lchild != -1)
InOrder(T[root].lchild);
}
queue<int>que;
void levelOrder()
{
while (!que.empty())
{
int root = que.front();
que.pop();
if (flag)
cout << ' ';
cout << root;
flag = true;
if (T[root].rchild != -1)
que.push(T[root].rchild);
if (T[root].lchild != -1)
que.push(T[root].lchild);
}
cout << endl;
}
void solution()
{
cin >> N;
T.resize(N); FindRoot.resize(N);
for (int i = 0; i < N; i++)
{
cin >> temp1>>temp2;
if (temp1 != '-')
{
T[i].lchild = temp1 - '0';
FindRoot[temp1 - '0'] = true;
}
if (temp2 != '-')
{
T[i].rchild = temp2 - '0';
FindRoot[temp2 - '0'] = true;
}
}
int root;
for (int i = 0; i < N; i++)
{
if (FindRoot[i] == false)
{
root = i;
break;
}
}
flag = false;
que.push(root);
levelOrder();
flag = false;
InOrder(root);
}

int main()
{
freopen("1.txt", "r", stdin);
solution();
system("pause");
return 0;
}

测试数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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