leetcode_【106】从中序与后序遍历序列构造二叉树

1.题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

>       3
>      /  \
>     9    20
>    /  \
>   15   7
>

2.解题思路

中序9,3,15,20,7,后序 9,15,7,20,3

有如下特征：

1. 后序中最后一位1肯定是根结点，我们可以据此找到中序中根结点的位置root；
2. 中序中根结点左边就是左子树结点，右边就是右子树结点，即[左子树结点，根结点，右子树结点]，我们就可以得出左子树结点个数为int left = rootin - leftin;；
3. 后序中结点分布应该是：[左子树结点，右子树结点，根结点]；
4. 根据前一步确定的左子树个数，可以确定前序中左子树结点和右子树结点的范围；
5. 如果我们要后序遍历生成二叉树的话，下一层递归应该是：
   • 左子树：root.left = buildTree(中序左子树范围，后序左子树范围);；
   • 右子树：root.right = buildTree(中序右子树范围，后序左子树范围，);。
6. 每一层递归都要返回当前根结点root；

3.代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 执行用时 :
    42 ms, 在所有 Java 提交中击败了15.47%的用户
 内存消耗 :
    78.1 MB, 在所有 Java 提交中击败了5.17%的用户
class Solution {
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
            if(inorder.length == 0||postorder.length == 0)
                return null;
            //根节点为后序遍历的最后一个节点
            TreeNode root = new TreeNode(postorder[postorder.length-1]);
            for(int i = 0;i<inorder.length;i++){
              //找到根节点在中序遍历的点，左边为根的左节点，右边为根的右节点
                if(inorder[i] == postorder[postorder.length-1]){
               //递归构建左子树，此时,中序缩小为[0,i),后序的范围缩小为[0,i]
                    root.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
              //递归构建右子树,中序缩小为[i+1,len),后序的范围缩小为[i,len-1),
                    root.right = buildTree(Arrays.copyOfRange(inorder,i+1,inorder.length),Arrays.copyOfRange(postorder,i,postorder.length-1));
                    break;
                }
            }
            return root;
        }
}

4.提交记录