25.从中序与后序遍历序列构建二叉树

题目描述

根据一棵树的中序遍历和后序遍历构造二叉树（树中没有重复的元素）。

解题思路

首先了解树的中序遍历和后序遍历概念。中序遍历是先遍历根节点的左子树，然后遍历根节点，最后遍历根节点的右子树。后序遍历是先遍历根节点的左子树，然后遍历根节点的右子树，最后遍历根节点。

由上可知，后序遍历序列的最后一个值即根节点的值。创建根节点，然后去中序遍历序列中查找当前值的索引，索引左侧即树的左子树，索引右侧即树的右子树，然后根据索引左侧值的数量和索引右侧值的数量确定左子树和右子树的节点数，进而确定后序遍历中左子树和右子树的索引位置。

最后递归的去创建根节点的左子树和右子树。

Code：

class Solution{
    public TreeNode buildTree(int[] inorder,int[] postorder){
        if(inorder.length == 0){
            return null;
        }
        if(inorder.length == 1){
            return new TreeNode(inorder[0]);
        }
        int cur = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(cur);
        int leftIndex = -1;
        for(int i = 0;i < inorder.length;i++){
            if(inorder[i] == cur){
                leftIndex = i;
            }
        }
        root.left = buildTree(Arrays.copyOfRange(inorder,0,leftIndex),
                              Arrays.copyOfRange(postorder,0,leftIndex));
        root.right = buildTree(Arrays.copyOfRange(inorder,leftIndex + 1,inorder.length),                   Arrays.copyOfRange(postorder,leftIndex,postorder.length - 1));
        return root;
    }
}

观察上述代码，可以发现，由于每次都要复制数组，造成的空间复杂度和时间复杂度过高，我们可以采用记录索引的方式优化代码。

Code

class Solution{
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder,postorder,0,inorder.length - 1,0,postorder.length - 1);
    }
    private TreeNode build(int[] inorder,int[] postorder,int a,int b,int m,int n){
        if(b - a < 0){
            return null;
        }
        if(b == a){
            return new TreeNode(inorder[b]);
        }
        int cur = postorder[n];
        TreeNode root = new TreeNode(cur);
        int leftIndex = 0;
        for(int i = a;i < b + 1;i++){
            if(inorder[i] == cur){
                leftIndex = i;
            }
        }
        root.left = build(inorder,postorder,a,leftIndex - 1,m,n - 1 - b + leftIndex);
        root.right = build(inorder,postorder,leftIndex + 1,b,leftIndex - a,n -1);
        return root;
    }
}