题意：

给定一棵节点数为 $n$ 的二叉树的前序遍历和后序遍历的序列，求出该二叉树中序遍历的序列

解法一（递归求解）

我们考虑 $dfs(pre,preL,preR,suf,sufL,sufR)$ 表示求解前序遍历的序列为 $pre[preL]\sim pre[preR]$ ，后序遍历的序列为 $suf[sufL]\sim suf[sufR]$ 的一棵子二叉树的答案

1. 根据前序遍历的性质，我们知道当前子树的根节点为 $pre[preL]$

2. 根据前序遍历（根、左、右）的顺序，我们知道当前节点的左子树的根节点为 $pre[preL+1]$

3. 接下来我们考虑求解当前左子树的节点个数

（1）我们知道对于后序遍历来说，根节点是最后被访问到的，那么我们先求出在后序遍历序列中，左子树根节点在后序遍历序列中的位置 $lpos$

（2）显然可得左子树的大小为 $lpos-sufL+1$ ，我们记 $lsize=lpos-sufL+1$

（3）由以上我们可得左子树对应的子问题为： $dfs(pre,preL+1,preL+lsize,suf,sufL,lpos)$

4. 接下来我们考虑求解当前右子树对应的子问题

（1）根据前序遍历（根、左、右）的顺序，我们可知右子树的根节点为 $pre[preL+lsize+1]$

（2）根据后序遍历（左、右、根）的顺序，我们可知右子树对应后序遍历的范围为 $[lpos+1,sufR]$

（3）由此我们可以得出右子树对应的子问题为： $dfs(pre,preL+lsize+1,preR,suf,lpos+1,sufR)$

于是我们可以按照中序遍历（左、根、右）的顺序，先求解左子树的子问题，再将当前节点加入到答案数组中，最后求解右子树的子问题

代码：

class Solution {
public:
    vector<int> ans;
    void dfs(vector<int>& pre,int preL,int preR,vector<int>& suf,int sufL,int sufR){
        if(preL>preR||sufL>sufR)return;//区间不存在，直接返回
        if(preL==preR){//区间只有一个节点
            ans.push_back(pre[preL]);
            return;
        }
        int u=pre[preL];//当前子树根节点
        int lson=pre[preL+1];//当前子树左子树根节点
        int lpos=sufL;//当前子树左子树根节点在suf数组中的位置
        while(suf[lpos]!=lson)lpos++;
        int lsize=lpos-sufL+1;//左子树大小
        dfs(pre,preL+1,preL+lsize,suf,sufL,lpos);//左子树
        ans.push_back(u);
        dfs(pre,preL+lsize+1,preR,suf,lpos+1,sufR);//右子树
    }
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        ans.clear();//多测清空
        dfs(pre,0,n-1,suf,0,n-1);//整棵树
        return ans;
    }
};

时间复杂度： $O(n^2)$ ，递归所有子问题相当于将所有节点访问一遍并且建树，因为有 $n$ 个节点，故代价是 $O(n)$ 的，程序中有寻找 $lpos$ 的过程，最坏情况每一次寻找都是 $O(n)$ 的，故总的时间复杂度是 $O(n^2)$

空间复杂度： $O(n)$ ，程序中的 $ans$ 数组是 $O(n)$ 大小的，递归的深度也为 $O(n)$ ，故总的空间复杂度为 $O(n)$

解法二（hash优化查找速度）

在解法一中，程序的主要时间瓶颈为寻找 $lpos$ 的过程，我们可以开一个数组 $pos$ 直接记录每一个节点在 $suf$ 数组中的位置

这样寻找 $lpos$ 就由 $O(n)$ 变为 $O(1)$ 了

代码：

class Solution {
public:
    int pos[100001];
    vector<int> ans;
    void dfs(vector<int>& pre,int preL,int preR,int sufL,int sufR){
        if(preL>preR||sufL>sufR)return;//区间不存在
        if(preL==preR){//区间只有一个节点
            ans.push_back(pre[preL]);
            return;
        }
        int u=pre[preL];//当前根节点
        int lson=pre[preL+1];//左子树根节点
        int lpos=pos[lson];//最子树根节点位置
        int l_size=lpos-sufL+1;
        dfs(pre,preL+1,preL+l_size,sufL,lpos);//左子树
        ans.push_back(u);
        dfs(pre,preL+l_size+1,preR,lpos+1,sufR);//右子树
    }
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        ans.clear();
        memset(pos,0,sizeof pos);
        for(int i=0;i<n;i++){
            pos[suf[i]]=i;//直接记录
        }
        dfs(pre,0,n-1,0,n-1);//整棵树
        return ans;
    }
};

时间复杂度： $O(n)$ ，递归所有子问题相当于将所有节点访问一遍并且建树，因为有 $n$ 个节点，故代价是 $O(n)$ 的，递归函数中的时间代价是 $O(1)$ 的，故总的时间复杂度为 $O(n)$

空间复杂度： $O(n)$ ，程序中的 $pos$ 数组都是 $O(n)$ 大小的，递归的深度也为 $O(n)$ ，故总的空间复杂度为 $O(n)$

题解 | #中序序列#

题意：

解法一（递归求解）

解法二（hash优化查找速度）