中后二叉建树

// 浪漫恻隐
// 中序 后续 建树
// 数组写 https://blog.csdn.net/qq_33957603/article/details/117093898?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165028864316780261969875%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=165028864316780261969875&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-6-117093898.142^v9^pc_search_result_control_group,157^v4^control&utm_term=%E6%B5%AA%E6%BC%AB%E4%BE%A7%E5%BD%B1+pta&spm=1018.2226.3001.4187
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* l;
    TreeNode* r;
};

// TODO(递归到当前这一层， mid 为 当前构建这颗树中序节点 ，hou 当前的后序遍历节点)
// TODO len 当前构建这颗树的节点个数
TreeNode* build(int mid[], int hou[], int len) {
    if (len == 0) return NULL;
    // TODO 找到根节点
    int tmp = hou[len - 1];
    int index = -1;
    for(int i = 0; i < len; i++) {
        if (tmp == mid[i]) {
            index = i;
            break;
        }
    }
    // todo 左子树个数 index , 右子树个数  len - index - 1
    TreeNode* root = new TreeNode();
    root->val = tmp;
    // TODO 找到了根节点 index
    // TODO 1. 0 ~ index - 1 中序中左子树的下表范围
    // TODO 2. index + 1 ~ len - 1 中序中you子树的下表范围
    // tOdo 3. 0 ~  index - 1  后续中左子树的个数
    // todo 4. index ~ len - 2
    // TODO 建左子树
    root->l = build(mid, hou, index);
    // todo 建uou子树
    // todo 将数组头向后挪 index + 1位
    root->r = build(mid + index + 1, hou + index, len - index - 1);
    return root;
}
int a[25], b[25];
vector<int> ans1, ans2;
void bfs(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        int len = q.size();
        for(int i = 0;i < len; i++) {
            TreeNode* tmp = q.front();
            q.pop();
//            cout << root->val << endl;
            if (tmp->l != NULL) q.push(tmp->l);
            if (tmp->r != NULL) q.push(tmp->r);
            
            if (i == 0) ans1.push_back(tmp->val);

            if(i == len - 1) ans2.push_back(tmp->val);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];

    TreeNode* root = build(a, b, n);
    bfs(root);
    cout << "R:";
    for(auto i : ans2) {
        cout << " " << i;
    }
    cout << endl;

    cout << "L:";
    for(auto i : ans1) {
        cout << " " << i;
    }
    cout << endl;
    return 0;
}