leetcode_【105】从前序与中序遍历序列构造二叉树

1.题目描述

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

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

例如，给出

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

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

2.解题思路

同【剑指offer_4】

前序3,9,20,15,7 ，中序9,3,15,20,7；

有如下特征：

1. 前序中左起第一位3肯定是根结点，我们可以据此找到中序中根结点的位置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; }
 * }
 */
 执行用时 :
    43 ms, 在所有 Java 提交中击败了15.42%的用户
 内存消耗 :
    76.5 MB, 在所有 Java 提交中击败了6.76%的用户
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0)
            return null;
        //根节点
        TreeNode root = new TreeNode(preorder[0]);
        for(int i = 0;i<inorder.length;i++){
            //找到根节点在中序遍历的点，左边为根的左节点，右边为根的右节点  
            if(preorder[0] == inorder[i]){
             //递归构建左子树，此时前序的范围缩小为[1,i],中序缩小为[0,i)     
                root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
             //递归构建右子树,此时前序的范围缩小为[i+1,len),中序缩小为[i+1,len)   
                root.right = buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),Arrays.copyOfRange(inorder,i+1,inorder.length));
                break;
            }
        }
        return root; 
    }
}

执行用时32ms的范例：

/**

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.length) {
            return null;
        }
        return buildHelper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    private TreeNode buildHelper(int[] preorder, int[] inorder, int preL, int preR, int inL, int inR) {
        if (preL > preR) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preL]);
        int rootIdx = -1;
        for (int i = inL; i <= inR; i ++) {
            if (inorder[i] == preorder[preL]) {
                rootIdx = i;
                break;
            }
        }
        if (rootIdx == -1) { return null; }
        root.left = buildHelper(preorder, inorder, preL + 1, rootIdx - inL + preL, inL, rootIdx - 1);
        root.right = buildHelper(preorder, inorder, rootIdx - inL + preL + 1, preR, rootIdx + 1, inR);
        return root;
    }
}

4.提交记录