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 1
    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
    86
    87
    88
    89
    90
    91
    92
    93
    94
    #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;
    }