题解 | #中序序列#

##题意 给定一棵有$nn$n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。 若某节点只有一个子结点，则此处将其看作左儿子结点

##0分做法：枚举 将所有可能出现的中序序列枚举，并根据中序遍历和前序遍历计算后序遍历，若后序遍历与所给相等说明得到所需中序遍历，由于所有不同的序列有n!种，故该方法不可行

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 二叉树节点数量
     * @param pre intvector 前序序列
     * @param suf intvector 后序序列
     * @return intvector
     */
    
        vector<int> tmp;
        int N;
        vector<int> ans,pre,suf;
    void calc(int pr,int in,int len)
    {
        if(!len) return;//若子树为空返回
        int k=in;
        int now=0;
        for(;now<len;++now)
        {
            if(ans[now]==k) break;
        }
        calc(pr,in+1,now);//搜索左子树
        calc(pr+now+1,in+now+1,len-N-1);//搜索右子树
        tmp.push_back(ans[in]);//将根节点存入答案
    }
        vector<int> solve(int n, vector<int>& Pre, vector<int>& Suf) {
        // write code here
        pre=Pre;
        suf=Suf;
            N=n;
        for(int i=1;i<=n;i++) ans[i]=i;
        do
        {
            //bool flag=true;
            tmp=vector<int>(n+1,0);
            calc(0,0,n);//根据Pre和tmp为前中计算后序
            if(tmp==Suf) break;//若计算出的后序等于题给后序说明ans为中序
        }
        while(next_permutation(ans.begin()+1, ans.end()));//
        return ans;
    }
};

时间复杂度:$O(n!)O(n!)$O(n!)，需要枚举n!种可能的中序序列。 空间复杂度:$O\left(n\right)O(n)$O(n)，使用了$O\left(n\right)O(n)$O(n)的栈空间与储存数组。

##100分做法：搜索 首先利用前序遍历和后序遍历求出具体的二叉树（注意到“若某节点只有一个子结点，则此处将其看作左儿子结点”，可以证明这样的二叉树是惟一的），然后已知二叉树求中序遍历。 代码如下

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 二叉树节点数量
     * @param pre intvector 前序序列
     * @param suf intvector 后序序列
     * @return intvector
     */
    bool isLegal(int a,int b,int c,int d)
    {return c>=a&&d>=b;}
    void dfs(int preL,int posL,int preR,int posR)
    {
        if(!isLegal(preL,posL,preR,posR)) {return;/*puts("illegal");*/}//判断区间合法性
        else if(preL==preR) {ans.push_back(pre[preL]);return;}//pre[preL]是该树的根
        int tmp=posL;
        for(;suf[tmp]-pre[preL+1];) tmp++;tmp++;
        dfs(preL+1,posL,preL+tmp-posL,tmp-1);//确定左子树的形状
        ans.push_back(pre[preL]);//按中序遍历顺序维护答案
        dfs(preL+tmp-posL+1,tmp,preR,posR);//确定右子树的形状
    }
    vector<int>ans,pre,suf;
    vector<int> solve(int n, vector<int>& Pre, vector<int>& Suf) {
        // write code here
        pre=Pre;
        suf=Suf;
        dfs(0,0,n-1,n-1);//确定整颗树的形状
        return ans;
    }
};

时间复杂度：$O\left(n\right)O(n)$O(n)，两个序列只需要扫描一遍就能得到结果。 空间复杂度：$O\left(n\right)O(n)$O(n)，需要$O\left(n\right)O(n)$O(n)的栈空间。

##相关知识：二叉树的遍历 二叉树的遍历一般分为深度优先和广度优先两种，深度优先又细分为前序遍历(pre-order traversal)、中序遍历(in-order traversal)和后序遍历(post-order traversal)三种。

下面三张图展示了三种遍历的顺序

前序： 中序： 后序： 因此我们可以使用递归的方法利用前序序列与后序序列，在限定条件下得出唯一子树，具体为先找到该树的根，再将树分为左右子树，在子树中递归执行，最后将整棵树的形状得出。