题解 | NC612#中序序列#

题目描述

给定一棵有n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。
若某节点只有一个子结点，则此处将其看作左儿子结点
示例1
输入：5,[3,2,1,4,5],[1,5,4,2,3]
返回值：[1,2,5,4,3]
图片说明

题目分析

在给定两个遍历序列，求另一种遍历序列中：
①给定先序序列和中序序列，可以唯一确定树，后序遍历唯一；
②给定后序序列和中序序列，可以唯一确定树，先序遍历唯一；
③给定先序序列和后序序列，不能唯一确定树；
前两种情况，能唯一确定树的原因是能够根据两个序***定根结点的左右子树范围（主要是中序序列分隔了左右子树）；
第三种情况，不能确定左右子树的范围，因为当某结点只有一个子节点时，无法确定它是左子节点还是右子节点，如图，两种情况的先序和后序是相同的。
图片说明
当题目中表明，只有一个结点则看做左子节点，那就可以唯一确定树了。
当先序遍历i还未到末尾时，则将i作为根节点，i+1一定是它的左子节点（若存在子节点，首先考虑左子节点），根据左子节点 i+1的值，可以在后序遍历（左-右-根）中，获得左右子树的范围：
图片说明

解题思路

方法1：重建二叉树，再进行中序遍历
重建二叉树的过程，就是确定根的左右子节点的过程，然后再继续遍历左右子节点，基本思路：
1.若存在子节点一定为左子节点，所以先序遍历中，根结点i后面若还有数，则i+1一定是左子节点；
2.根据i+1的值，在后序遍历中找到左子节点的位置 j ，然后确定左子树长度和右子树长度；
3.这里一定要限制每一次递归的数组范围，所以设置pl 和 pr，sl和sr来记录递归范围；
4.当在后序遍历中找到了左子节点的位置 j ，则在后序遍历中 sl ~ j是左子树范围，j+1 ~ sr是右子树范围，同时也可以知道在先序遍历中的范围（知道左右子树的长度了），pl+1 ~ pl+1+j-sl是左子树范围，pl+1+j-sl+1 ~ pr是右子树范围；
5.最后对子树进行同样的递归遍历，直到所有的都遍历完成，对数进行中序遍历得到结果。

方法2：不创建树，直接在遍历过程中，获取中序遍历序列
在方法1中，我们需要不断创建树结点，最后再重新遍历一遍树，才能得到结果，其实可以在遍历的过程中，直接使用结果数组记录遍历的值，因为是中序遍历，所以需要在所以的左子节点都建立完成后，才将值赋给res数组，这里需要使用全局变量index，来标记当前记录的数据个数。

代码实现

方法1重建二叉树，再进行中序遍历

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    TreeNode(int val){
        this.val = val;
    }
}

    int index=0;
    public int[] solve (int n, int[] pre, int[] suf) {
        // write code here
        // 重建二叉树
        // 可以根据先序（根、左、右），后序（左、右、根）
        TreeNode root = buildTree(pre, 0, n-1, suf, 0, n-1);
        int[] res = new int[n];
        // 进行中序遍历
        midDfs(root, res);
        return res;
    }

    public TreeNode buildTree(int[] pre, int pl, int pr, int[] suf, int sl, int sr){
        // 超过范围返回空
        if(sl > sr) return null;
       // 将后序遍历的最后一个元素作为根节点
        TreeNode root = new TreeNode(suf[sr]);
        for(int i=sl;i<=sr;i++){
            // 在后序遍历中，找到根的左子节点pl+1
            if(pl<pr && suf[i] == pre[pl+1]){
                // 确定左子树范围
                root.left = buildTree(pre, pl+1, pl+1+i-sl, suf, sl, i);
                // 确定右子树范围
                root.right = buildTree(pre, pl+2+i-sl, pr, suf, i+1, sr-1);
                break;
            }
        }
        return root;
    }

    public void midDfs(TreeNode root, int[] res){
        if(root == null) return;
        midDfs(root.left, res);
        res[index++] = root.val;
        midDfs(root.right, res);
    }

时间复杂度： $O(n^2)$ ，在后序遍历中找左子节点最坏需要n次，而递归深度最多为n，所以时间花费最多为n^2；
空间复杂度： $O(n)$ ，需要使用额外n空间的递归栈以及创建树所需要的n的空间；

方法2：不创建树，直接在遍历过程中，获取中序遍历序列

    int index=0;
    int[] res;
    public int[] solve (int n, int[] pre, int[] suf) {
        // 可以直接在建树的过程中，给数组赋值
        res = new int[n];
        buildTree(pre, 0, n-1, suf, 0, n-1);
        return res;
    }

    public void buildTree(int[] pre, int pl, int pr, int[] suf, int sl, int sr){
        if(sl > sr) return ;
        if(sl == sr){
            // 碰到子树只有一个值，则直接记录下来
            res[index++] = suf[sr];
            return;
        }
        for(int i=sl;i<=sr;i++){
            // 在后序遍历中找到左子节点的位置i
            if(pl<pr && suf[i] == pre[pl+1]){
                // 获取左子树范围（后序：sl~i）
                buildTree(pre, pl+1, pl+1+i-sl, suf, sl, i);
                // 中序遍历（先左子节点）
                res[index++] = suf[sr];
                // 获取右子树范围（后序：i+1~sr-1）
                buildTree(pre, pl+2+i-sl, pr, suf, i+1, sr-1);
                break;
            }
        }
    }

时间复杂度： $O(n^2)$ ，在后序遍历中找左子节点最坏需要n次，而递归深度最多为n，所以时间花费最多为n^2；
空间复杂度： $O(n)$ ，需要使用额外n空间的递归栈，这里可以不用创建树；