中序序列 牛客编程巅峰赛S1第9场 - 青铜&白银

我们知道，只想知道一棵树的前序遍历和后序遍历是求不出中序遍历的。
但是，因为题目多了一个条件【若某节点只有一个子结点，则此处将其看作左儿子结点】。所以可以求出唯一的一个中序遍历。

在二叉树的前序遍历中，第一个数字总是树的根结点，根结点右边的第一个结点总是左儿子结点。
在该二叉树的后序遍历中，知道了该根结点和其左儿子在后序遍历中的下标后，夹在根结点和其左儿子之间的结点是根结点的右子树。在左儿子的左边部分结点是该左儿子的子树。

既然我们已经找到了左、右子树的前序遍历和中序遍历，我们可以用同样的方法分别取构建左右子树。也就是说，接下来可以用递归的方法完成。

import java.util.*;

public class Solution {
    /**
     * 返回所求中序序列
     * @param n int整型 二叉树节点数量
     * @param pre int整型一维数组 前序序列
     * @param suf int整型一维数组 后序序列
     * @return int整型一维数组
     */
    int len = 0;
    public int[] solve (int n, int[] pre, int[] suf) {
        // write code here
        int[] v = new int[n];
        deal(0,n-1,pre,0,n-1,suf,v);
        return v;
    }

    void deal(int pl, int pr, int[] pre, int sl, int sr, int[] suf, int[] v){
        if(pl > pr)
            return;
        if(pl == pr){
            v[len++] = pre[pl];
            return;
        }
        int pos = -1;
        for(int i = sl; i <= sr; i++){
            if(suf[i] == pre[pl + 1])
                pos = i;//在后序遍历找到根结点的左儿子的位置
        }
        deal(pl + 1, pos - sl + pl + 1, pre, sl, pos, suf, v);//递归左子树
        v[len++] = pre[pl];
        deal(pos - sl + pl + 2, pr, pre, pos + 1, sr - 1, suf, v);//递归右子树
    }
}

在函数deal中，我们先根据前序遍历的第一个数字确定根结点，第二个数字确定根结点的左儿子，接下来在后序遍历找到根结点的位置，这样就能确定左右子树结点的数量。在前序遍历和后序遍历的序列中划分左、右子树的结点的值之后，我们就可以递归调用deal，去分别确定它的左右子树。