二叉树 | 由层序、中序序列建树

PAT考试超爱考二叉树，中序+先序/后序还原二叉树，先序+后序判断能否还原出唯一的二叉树都已经考过了。好像就差从中序、层序序列还原二叉树了。
附上一位PAT前辈的博客，梳理了所有的由两种遍历序列还原二叉树的情况。
所以，今天来搞一波——由中序、层序还原二叉树，万一考了就赚了= =

思路

• 还是递归

• 需要注意的是

  • 区别于前序/中序/后序，层序序列中子树是不一定连续的，左右子树的结点交替出现。
  • 各个级别的子树中，最先出现在层序序列中的那个结点，一定是这个子树的根结点。

• 基于以上两点，写了函数在层序中找当前子树的根结点，再把根结点提供给中序，从而划分开左右子树。
  其实还是中序划分左右子树，其他序(先序/后序/层序)提供根结点信息的套路。

#include <cstdio>

#define MAXN 32
using namespace std;
int level_order[MAXN], in_order[MAXN];
struct Node {
    int key;
    Node *lchild = NULL, *rchild = NULL;
};
int nn;

int find_lvl_root_pos(int l, int r, int rpos) {
    bool flag = true;
    while (flag) {
        for (int i = l; i <= r; ++i) {
            if (in_order[i] == level_order[rpos]) {
                flag = false;
                break;
            }
        }
        if (flag) rpos++;
    }
    return rpos;
}

Node *createTree(int in_st, int in_ed, int lvl_i) {
    if (in_st > in_ed || lvl_i >= nn) return NULL;
    if (in_st == in_ed)
        return new Node{in_order[in_st], NULL, NULL};
    int root_key = level_order[lvl_i], pos = in_st;
    while (in_order[pos] != root_key && pos < nn)
        pos++;
    Node *root = new Node;
    root->key = root_key;
    if (pos == in_ed) {// lchild not null, rchild null
        root->lchild = createTree(in_st, in_ed - 1, find_lvl_root_pos(in_st, in_ed - 1, lvl_i + 1));
    } else if (pos == in_st) {// lchild null, rchild not null
        root->rchild = createTree(in_st + 1, in_ed, find_lvl_root_pos(in_st + 1, in_ed, lvl_i + 1));
    } else { // both not null
        root->lchild = createTree(in_st, pos - 1, find_lvl_root_pos(in_st, pos - 1, lvl_i + 1));
        root->rchild = createTree(pos + 1, in_ed, find_lvl_root_pos(pos + 1, in_ed, lvl_i + 2));
    }
    return root;
}

void pre_order_traverse(Node *root) {
    printf("%d ", root->key);
    if (root->lchild)pre_order_traverse(root->lchild);
    if (root->rchild)pre_order_traverse(root->rchild);
}

int main() {
    scanf("%d", &nn);
    for (int i = 0; i < nn; ++i) scanf("%d", &in_order[i]);
    for (int i = 0; i < nn; ++i) scanf("%d", &level_order[i]);
    Node *root = createTree(0, nn - 1, 0);
    pre_order_traverse(root);
    return 0;
}