题意:

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

解法一(递归求解)

我们考虑表示求解前序遍历的序列为,后序遍历的序列为的一棵子二叉树的答案
    1. 根据前序遍历的性质,我们知道当前子树的根节点为
    2. 根据前序遍历(根、左、右)的顺序,我们知道当前节点的左子树的根节点为
    3. 接下来我们考虑求解当前左子树的节点个数
        (1)我们知道对于后序遍历来说,根节点是最后被访问到的,那么我们先求出在后序遍历序列中,左子树根节点在后序遍历序列中的位置
        (2)显然可得左子树的大小为,我们记
                                   
        (3)由以上我们可得左子树对应的子问题为:
    4. 接下来我们考虑求解当前右子树对应的子问题
        (1)根据前序遍历(根、左、右)的顺序,我们可知右子树的根节点为
        (2)根据后序遍历(左、右、根)的顺序,我们可知右子树对应后序遍历的范围为
                                
        (3)由此我们可以得出右子树对应的子问题为:
于是我们可以按照中序遍历(左、根、右)的顺序,先求解左子树的子问题,再将当前节点加入到答案数组中,最后求解右子树的子问题
代码:
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;
    }
};
时间复杂度:,递归所有子问题相当于将所有节点访问一遍并且建树,因为有个节点,故代价是的,程序中有寻找的过程,最坏情况每一次寻找都是的,故总的时间复杂度是
空间复杂度:,程序中的数组是大小的,递归的深度也为,故总的空间复杂度为

解法二(hash优化查找速度)

解法一中,程序的主要时间瓶颈为寻找的过程,我们可以开一个数组直接记录每一个节点在数组中的位置
这样寻找就由变为
代码:
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;
    }
};
时间复杂度:递归所有子问题相当于将所有节点访问一遍并且建树,因为有个节点,故代价是的,递归函数中的时间代价是的,故总的时间复杂度为
空间复杂度:,程序中的数组都是大小的,递归的深度也为,故总的空间复杂度为