Invert a Binary Tree

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

The main idea of the topic ：
Swap the left and right subtrees of a binary tree , And output the sequence traversal and middle sequence traversal after exchange .

ps:（ The title is not difficult. , I wrote this blog because there is an algorithm problem in the chapter of binary tree in Wang daoshu, which is to exchange the left of binary tree 、 Right subtree , Happened to be here today pta See this problem above , Just do it by the way , Then write this blog , I hope that helps .）

Their thinking ： Recursive algorithm is used to realize the left-hand transformation of commutative binary tree 、 Right subtree , First exchange nodes k The left of the child 、 Right subtree , Exchange again k The right of the node, the left of the child 、 Right subtree , Finally exchange k The left side of the node 、 The right child , When the node is empty, the recursion ends .

#include<bits/stdc++.h>
using namespace std;
struct binary_tree
{
    
    int data;
    int lchild, rchild;
}node[15];
int n;
bool visited[15] = {
    false};
int build_tree() {
    
    scanf("%d", &n);
    char left, right;
    for(int i = 0; i < n; i++) {
    
        node[i].data = i;
        cin >> left >> right;
        if(left == '-') node[i].lchild = -1;
        else {
    
            node[i].lchild = (left - '0');
            visited[left - '0'] = true;
        }
        if(right == '-') node[i].rchild = -1;
        else {
    
            node[i].rchild = (right - '0');
            visited[right - '0'] = true;
        }
    }
    for(int i = 0; i < n; i++) {
     // Return root node 
        if(!visited[i]) return i;
    }
}
void invert(int k) {
     // Recursively swap left 、 Right subtree 
    if(k == -1) return;
    invert(node[k].lchild);
    invert(node[k].rchild);
    swap(node[k].lchild, node[k].rchild);
}
void levelorder(int root) {
     // Sequence traversal 
    queue<binary_tree>q;
    q.push(node[root]); //  Root in line 
    vector<int> ans;
    while(!q.empty()) {
    
        binary_tree top = q.front();
        q.pop();
        ans.push_back(top.data);
        if(top.lchild != -1) q.push(node[top.lchild]);
        if(top.rchild != -1) q.push(node[top.rchild]);
    }
    printf("%d", ans[0]);
    for(int i = 1; i < ans.size(); i++) printf(" %d", ans[i]);
    puts("");
}
vector<int>inorder_ans; // To ensure that no extra spaces are output when the last node is output , First save the answers with an array 
void inorder(int k) {
     // In the sequence traversal 
    if(k == -1) return;
    inorder(node[k].lchild);
    inorder_ans.push_back(node[k].data);
    inorder(node[k].rchild);
}
void print_inorder() {
     // Print the middle order traversal sequence 
    printf("%d", inorder_ans[0]);
    for(int i = 1; i < inorder_ans.size(); i++) printf(" %d", inorder_ans[i]);
}
int main() {
    
    int root = build_tree();
    // for(int i = 0; i < n; i++) {
    
    // cout << node[i].lchild << " " << node[i].rchild << endl;
    // }
    // cout << endl;
    invert(root);
    // for(int i = 0; i < n; i++) {
    
    // cout << node[i].lchild << " " << node[i].rchild << endl;
    // }
    levelorder(root);
    inorder(root);
    print_inorder();
    return 0;
}