Construct Binary Tree from Preorder and Inorder Traversal

iven preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

给定一棵树的中序遍历和前序遍历，构造出这棵树。我们可以通过前序遍历序列的第一个元素判断出每个子树的根节点，然后在中序遍历序列找到这个根节点，假设这个根结点在i位置，那么在inorder[i]左边的就是左子树的元素，在inorder[i]右边的就是右子树的元素。用递归来完成。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        int i;
        for(i = 0; i < inorder.length; i++) {
            if(preorder[0] == inorder[i])
                break;
        }
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
        root.right = buildTree(Arrays.copyOfRange(preorder, i + 1, preorder.length), Arrays.copyOfRange(inorder, i + 1, 
        inorder.length));
        return root;
    }
}

上面的代码每次递归都要在中序遍历序列中找当前的根节点，如果我们用一个哈希表来存储中序遍历序列的值和下标，那么每次查找的时间就可以缩减为O(1)，这样大大优化的算法的效率。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length == 0) return null;
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for(int i = 0; i < inorder.length; i++)
            hm.put(inorder[i], i);
        return getTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, hm);
    }
    public TreeNode getTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap<Integer, Integer> hm) {
        if(preStart > preEnd || inStart > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int position = hm.get(root.val);
        int leftNums = position - inStart;
        root.left = getTree(preorder, preStart + 1, preStart + leftNums, inorder, inStart, position - 1, hm);
        root.right = getTree(preorder, preStart + leftNums + 1, preEnd, inorder, position + 1, inEnd, hm);
        return root;
        
    }
}