【PAT A1020】通过中序和后续遍历还原二叉树并进行层序遍历

复习一下基础数据结构，这是以前没有搞明白的题目，现在搞明白了，建议画图理解
题目链接：PAT A1020

规律

① 后续序列中最后一个是根节点
② 中序序列中根节点左边是左子树，右边是右子树

所以：

• 找到中序序列中的根节点位置
• 然后将新树的范围划定出来：
  ① 中序左子树为根节点左边
  ② 右子树为根节点右边；
  ③ 后序序列左子树为左边的n个（n为中序左子树数目）
  ④ 后序右子树为剩下的部分（不包含最后一个根节点）
• 递归地创建左子树和右子树

代码

#include <bits/stdc++.h>

#define MAX 50
using namespace std;
int n;
//后续序列
int post_order[MAX];
//中序序列
int in_order[MAX];
struct tree {
    int data;
    tree *left;
    tree *right;
};

//找到中序序列中的根节点位置
int findRoot(int root, int left, int right) {
    for (int i = left; i <= right; ++i) {
        if (root == in_order[i])
            return i;
    }
}

//范围全部为闭区间
//pl:后续序列开始（post_order left）
//pr:后续序列结束（post_order right）
//il:中续序列结束（in_order right）
//ir:中续序列结束（in_order right）
tree *create(int pl, int pr, int il, int ir) {
    if (pl > pr || il > ir) {
        return nullptr;
    }
    int root = post_order[pr];
    int rootPos = findRoot(root, il, ir);
    tree *t = new tree({root, nullptr, nullptr});
    int count = rootPos - il;
    //划定左子树范围
    t->left = create(pl, pl + count - 1, il, rootPos - 1);
    //划定右子树范围
    t->right = create(pl + count, pr - 1, rootPos + 1, ir);
    return t;
}

//层序遍历
void levelTraversal(tree *root) {
    bool flag = true;
    queue<tree *> que;
    que.push(root);
    while (!que.empty()) {
        tree *node = que.front();
        que.pop();
        if (node->left)que.push(node->left);
        if (node->right)que.push(node->right);
        if (flag) {
            cout << node->data;
            flag = false;
        } else {
            cout << " " << node->data;
        }
    }
}

//PAT 1020:Tree Traversals
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> post_order[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> in_order[i];
    }
    tree *root = create(0, n - 1, 0, n - 1);
    levelTraversal(root);
    return 0;
}