# PAT A1102

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 11

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

86

87

88

89

90

91

92

93

94

95#include "stdio.h"

//#include "math.h"

#include "string.h"

//#include "iostream"

//#include "stdlib.h"

#include "vector"

//#include "set"

//#include "map"

#include "stack"

#include "queue"

#include "algorithm"

using namespace std;

//typedef long long LL;

const int maxn = 30;

struct node{

int lchild;

int rchild;

}Node[maxn];

bool notRoot[maxn] = {false};//记录是否不是根结点，初始均是根结点

int n, num = 0;//n为结点个数，num为当前已经输出的结点个数

//print函数输出结点id的编号

void print(int id){

printf("%d", id);//输出id

num++;//已经输出的结点个数+1

if (num < n) {

printf(" ");

}else{

printf("\n");

}

}

//中序遍历

void inOrder(int root){

if (root == -1) {

return;

}

inOrder(Node[root].lchild);

print(root);

inOrder(Node[root].rchild);

}

//层次遍历

void BFS(int root){

queue<int> Q;

Q.push(root);

while (!Q.empty()) {

int now = Q.front();

Q.pop();

print(now);

if (Node[now].lchild != -1) Q.push(Node[now].lchild);

if (Node[now].rchild != -1) Q.push(Node[now].rchild);

}

}

//后序遍历 用于反转二叉树

void postOrder(int root){

if (root == -1) {

return;

}

postOrder(Node[root].lchild);

postOrder(Node[root].rchild);

swap(Node[root].lchild, Node[root].rchild);//交换左右孩子结点

}

//将输入的字符转换为-1或者结点编号

int strToNum(char c){

if (c == '-') {

return -1;

}else{

notRoot[c - '0'] = true;//标记c不是根节点

return c - '0';

}

}

//寻找根节点

int findRoot(){

for (int i = 0; i < n; i++) {

if (notRoot[i] == false) {

return i;//是根节点，返回

}

}

return -1;

}

int main(){

char lchild, rchild;

scanf("%d", &n);//结点个数

for (int i = 0; i < n; i++) {

scanf("%*c%c %c", &lchild, &rchild);//左右孩子结点

Node[i].lchild = strToNum(lchild);

Node[i].rchild = strToNum(rchild);

}

int root = findRoot();

postOrder(root);//翻转二叉树

BFS(root);

num = 0;

inOrder(root);

return 0;

}