NC204383 中序序列

题意

给了一颗树的前序序列和后序序列，求中序序列
如果某节点只有一个子节点，将其视为左节点

思路

为了按照中序序列“左、根、右”的顺序输出序列，我们需要用到递归，先递归左树、输出根、再递归右树。

以题目给出的示例一的树为例：
由于给了前序序列，所以我们知道3是根节点，3后边的2是他左子树的根节点
知道了左子树的根节点，题目又给了后序序列，所以我们可以去后序序列中找到那个左子树的根，再根据后序序列“左、右、根”的顺序确定左子树节点的个数和右子树节点的个数

知道了左右子树的长度就可以确定他们在前序序列和后序序列的区间，接下来只要以左树和右树为参数，分别递归调用自身，一直到区间里只剩一个节点（节点没有子节点）为止，就可以开始输出了

本地调试用的代码

#include <iostream>
#include <vector>

using namespace std;

vector<int> res;

/**
 * @brief 生成的后序序列直接储存在res里
 * @param pre intvector 前序序列
 * @param preL int 当前树区间的左端点
 * @param preR int 当前树区间的右端点
 * @param suf intvector 后序序列
 * @param sufL int 当前树区间的左端点
 * @param sufR int 当前树区间的右端点
 * @note 区间端点为res中的下标，从0开始
 */
void solve(vector<int> &pre, int preL, int preR, vector<int> &suf, int sufL, int sufR) {
    //区间不合法，直接退出
    if (preL > preR || sufL > sufR) {
        return;
    }
    //树没有子节点，直接输出根
    if (preL == preR) {
        res.push_back(pre[preL]);
        return;

    }
    int leftRoot = pre[preL + 1];   //前序遍历中左树的根
    int pos1 = sufL;   //leftRoot在suf中的下标
    //找到left在suf中的位置
    while (suf[pos1] != leftRoot) {
        pos1++;
    }
    //递归左树
    solve(pre, preL + 1, preL + (pos1 - sufL + 1), suf, sufL, pos1);
    //加上root
    res.push_back(pre[preL]);
    //递归右树
    solve(pre, preL + (pos1 - sufL + 1) + 1, preR, suf, pos1 + 1, sufR);
}


int main() {
    int temp;
    int n;  //节点数量
    vector<int> pre;    //前序序列
    vector<int> suf;    //后序序列
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        pre.push_back(temp);
    }
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        suf.push_back(temp);
    }
    solve(pre, 0, n - 1, suf, 0, n - 1);
    for (auto i:res) {
        cout << i << " ";
    }
}