PAT Advanced 1102 Invert A Binary Tree

Overview

PAT advanced 1102 Invert A Binary Tree just tests BFS, DFS, inorder, postorder tree traversal, simulate the process in O(N) time is enough.

PAT Advenced 1102 Invert A Binary Tree Problem

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

PAT Advenced 1102 Invert A Binary Tree Algorithm

This problem is not difficult, and as there is only 10 nodes at maximum case, it becomes a lot easier to pass OJ. Basically just simulate the process, invert the binary tree from bottom to top in a dfs manner, then traverse the inverted tree by BFS to print out level order, and gain by DFS to print out inorder sequence. The invert process is actually post order traveral, total time complexty is O(N) time, the following source code is accepted by PAT OJ to pass this 1102 Invert A Binary Tree problem.

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
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

struct TreeNode {
    public:
        int l, r;
        TreeNode() : l(-1), r(-1) {}
};

const static int MAXN = 10;
bool isRoot[MAXN];
TreeNode nodes[MAXN];
std::vector<int> in_order;
std::vector<int> level_order;

int findRoot(int n) {
    for (int i = 0; i < n; ++i) {
        if (isRoot[i])
            return i;
    }
    return -1;
}

void dfs(int root) {
    if (-1 == root) {
        return ;
    }

    dfs(nodes[root].l);
    dfs(nodes[root].r);

    std::swap(nodes[root].l, nodes[root].r);
}

void inorder(int root) {
    if (root == -1) {
        return ;
    }

    inorder(nodes[root].l);
    in_order.push_back(root);
    inorder(nodes[root].r);
}

void bfs(int root) {
    std::queue<int> q;
    q.push(root);

    while (!q.empty()) {
        int curr = q.front(); q.pop();
        level_order.push_back(curr);
        if (nodes[curr].l != -1)
            q.push(nodes[curr].l);
        if (nodes[curr].r != -1)
            q.push(nodes[curr].r);
    }
}

void print(std::vector<int> &seq) {
    int init = true;
    for (auto &e : seq) {
        if (init) {
            std::cout << e;
            init = false;
        } else {
            std::cout << ' ' << e;
        }
    }
    std::cout << std::endl;
}

int main() {
    int n;
    std::cin >> n;

    char c;

    for (int i = 0; i < n; ++i)
        isRoot[i] = true;

    for (int i = 0; i < n; ++i) {
        std::cin >> c;
        if (c != '-') {
            nodes[i].l = c - '0';
            isRoot[c - '0'] = false;
        }
        std::cin >> c;
        if (c != '-') {
            nodes[i].r = c - '0';
            isRoot[c - '0'] = false;
        }
    }

    int root = findRoot(n);
    dfs(root);
    inorder(root);
    bfs(root);
    print(level_order);
    print(in_order);

    return 0;
}

PAT Advenced 1102 Invert A Binary Tree Test Cases

Try a tree with one node, two nodes and zero nodes (zero nodes will not be present in the OJ test cases though).

Summary

PAT advanced 1102 Invert A Binary Tree just tests BFS, DFS, inorder, postorder tree traversal, simulate the process in O(N) time is enough.

Written on February 1, 2016