1102. Invert a Binary Tree (25)

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

#include<iostream>
#include<list>

using namespace std;
struct Node{
    
    int left;
    int right;
};

typedef Node* PNode;


int root;
int N;
int flag = false;

void levelOrder(PNode tree)
{
    int r;
    list<int> q;
    q.push_back(root);
    while(!q.empty())
    {
        if(flag == true) 
            cout << " ";
        else 
            flag = true; 
        r = q.front();
        q.pop_front();
        cout << r;
        if(tree[r].left != -1)
            q.push_back(tree[r].left);
        if(tree[r].right != -1)
            q.push_back(tree[r].right);
    }
    flag = false;
    cout << endl;
}
int toNum(char c)
{
    if(c=='-') return -1;
    return (c - '0');
}
void inorder(int r,PNode tree)
{
    if(tree[r].left != -1)
        inorder(tree[r].left,tree);
    if(flag != false)
        cout << " ";
    else
        flag = true;
    cout << r;
    if(tree[r].right != -1)
        inorder(tree[r].right,tree);
}


int main()
{
    int l,r;
    bool * findRoot;
    char c1,c2,c3;
    cin >> N;
    findRoot = new bool[N];
    PNode tree = new Node[N];
    for(int i=0; i<N; i++)
    {
        cin >> c1 >> c2;
        l = toNum(c1);
        r = toNum(c2);
        if(l!=-1) findRoot[l] = true;
        if(r!=-1) findRoot[r] = true;
        tree[i].left = r;
        tree[i].right = l;
    }
    for(int i=0; i<N; i++)
        if(findRoot[i] == false)
        {
            root = i;
            break;
        }
    levelOrder(tree);
    inorder(root,tree);

    return 0;
}