1102. Invert a Binary Tree (25)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> in;
struct node{
    int l, r;
};
vector<node> tree;
void inorder(int root){
    if(tree[root].l == -1 && tree[root].r == -1){//递归终止条件 到达根节点
        in.push_back(root);
        return;
    }
    if(tree[root].l != -1) inorder(tree[root].l);
    in.push_back(root);
    if(tree[root].r != -1) inorder(tree[root].r);
}

int main(){
    int n, root = 0;
    cin >> n;
    tree.resize(n);
    vector<int> isRoot(n);
    for (int i = 0; i < n; i++) {
        char c1, c2;
        cin >> c1 >> c2;
        tree[i].r = (c1 == '-' ? -1 : (c1 - '0'));
        tree[i].l = (c2 == '-' ? -1 : (c2 - '0'));
        if (tree[i].l != -1) isRoot[tree[i].l] = 1;
        if (tree[i].r != -1) isRoot[tree[i].r] = 1;
    }
    for (int i = 0; i < n; i++) {
        if(isRoot[i] == 0){  root = i;  break;}
    }
    queue<int> q;
    q.push(root);
    vector<int> level;
    while (! q.empty()) {
        int node = q.front();
        q.pop();
        if (tree[node].l != -1)
            q.push(tree[node].l);
        if (tree[node].r != -1)
            q.push(tree[node].r);
        level.push_back(node);
    }
    for (int i = 0; i < n; i++) {
        printf("%d%c", level[i], i == n-1 ? '\n' : ' ');
    }
    inorder(root);
    for (int i = 0; i < n; i++) {
        printf("%d%c", in[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}