题解 | #中序序列#

题意整理

给定一颗二叉树的先序遍历序列和后序遍历序列。
求中序遍历序列（如果某个节点只有一个子节点，则必是左子节点）。

方法一（递归+重建二叉树）

1.解题思路

在每次递归中，可以确定当前根节点在先序遍历开头处，后续遍历结尾处。在后续遍历中找到当前节点的第一个左子节点，则后续遍历中，该节点之前的一定是左子树(包括该节点)，该节点之后的一定是右子树（不包括当前根节点）。前序遍历怎么划分左右子树，可以参考后续遍历，因为一旦确认后续遍历的左右子树，对应左右子树节点个数也就确定了，而前序遍历划分的开始以及结束位置是知道的，根据开始处加上对应区间长度减一，即可得到左子树边界，同理确定右子树边界。
当前序遍历只有一个元素时，直接返回，作为当前层根节点。
当前序遍历没有元素时，递归终止。
重建二叉树之后，进行中序遍历，依次填充中序数组

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 二叉树节点数量
     * @param pre int一维数组 前序序列
     * @param suf int一维数组 后序序列
     * @return int一维数组
     */
    //结果数组
    int[] res;
    //游标
    int id=0;
    public int[] solve (int n, int[] pre, int[] suf) {
        //重建二叉树
        TreeNode root=build(pre,0,n-1,suf,0,n-1);
        res=new int[n];
        //给中序数组赋值
        inorder(root);
        return res;
    }

    //中序遍历
    private void inorder(TreeNode root){
        if(root==null) return;
        inorder(root.left);
        res[id++]=root.val;
        inorder(root.right);
    }

    //重建二叉树
    private TreeNode build(int[] pre,int startpre,int endpre, int[] suf,int startsuf,int endsuf){
        //递归终止条件
        if(startpre>endpre) return null;
        TreeNode root=new TreeNode(suf[endsuf]);
        for(int i=startsuf;i<=endsuf;i++){
            //在后序遍历中找到当前根节点的第一个左子节点
            if(startpre<endpre&&suf[i]==pre[startpre+1]){
                //递归左子树
                root.left=build(pre,startpre+1,startpre+1+i-startsuf,suf,startsuf,i);
                //递归右子树
                root.right=build(pre,startpre+2+i-startsuf,endpre,suf,i+1,endsuf-1);
                break;
            }
        }
        return root;
    }
}

//树结构
class TreeNode{
    TreeNode left=null;
    TreeNode right=null;
    int val;
    TreeNode(int val){
        this.val=val;
    }
}

3.复杂度分析

时间复杂度：寻找第一个左子节点，最坏情况下循环n次，递归的深度最坏情况下为n，所以时间复杂度为 $O(n^2)$ 。
空间复杂度：需要额外大小为n的递归栈，所以空间复杂度为 $O(n)$ 。

方法二（字典优化+合并赋值）

1.解题思路

思路和方法一大致相同，实现上做了一些优化。

优化一：使用哈希表对后续遍历的值和下标做映射，便于快速找到当前根节点的第一个左子节点。
优化二：在重建二叉树的过程中，直接对中序数组赋值。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 二叉树节点数量
     * @param pre int一维数组 前序序列
     * @param suf int一维数组 后序序列
     * @return int一维数组
     */
    //结果数组
    int[] res;
    //游标
    int id=0;
    //存放映射的字典
    HashMap<Integer,Integer> dic;
    public int[] solve (int n, int[] pre, int[] suf) {
        res=new int[n];
        dic=new HashMap<>();
        //将后序遍历的值和下标做映射
        for(int i=0;i<n;i++){
            dic.put(suf[i],i);
        }
        TreeNode root=build(pre,0,n-1,suf,0,n-1);
        return res;
    }

    private TreeNode build(int[] pre,int startpre,int endpre, int[] suf,int startsuf,int endsuf){
        //当前序遍历完成，则递归终止
        if(startpre>endpre) return null;
        TreeNode root=new TreeNode(suf[endsuf]);
        //只有一个值的情况
        if(startpre==endpre){
            res[id++]=pre[startpre];
            return root;
        } 
        //找到后续遍历中当前根节点的左子节点所在位置
        int i=dic.get(pre[startpre+1]);
        //递归左子树
        root.left=build(pre,startpre+1,startpre+1+i-startsuf,suf,startsuf,i);
        //给对应的中序数组赋值
        res[id++]=pre[startpre];
        //递归右子树
        root.right=build(pre,startpre+2+i-startsuf,endpre,suf,i+1,endsuf-1);
        return root;
    }
}

//树结构
class TreeNode{
    TreeNode left=null;
    TreeNode right=null;
    int val;
    TreeNode(int val){
        this.val=val;
    }
}

3.复杂度分析

时间复杂度：在 $O(1)$ 的时间复杂度内，就能寻找到第一个左子节点，递归的深度最坏情况下为n，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外大小为n的递归栈，所以空间复杂度为 $O(n)$ 。