Construct Binary Tree from Preor

• 描述
  Given preorder and inorder traversal of a tree, construct the binary tree.
  Note: You may assume that duplicates do not exist in the tree.

• 先序和中序、后序和中序可以唯一确定一棵二叉树

• 时间复杂度O(n)，空间复杂度O(logn)

// TreeNode.java
public class TreeNode {
    public TreeNode left;
    public TreeNode right;
    public int val;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// Solution.java
public class Solution {
    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        if(preOrder == null || inOrder==null || preOrder.length != inOrder.length)
            return null;
        return buildTree(preOrder, 0, preOrder.length-1,
                         inOrder,  0, inOrder.length-1);
    }

    public TreeNode buildTree(int[] preOrder, int preStart, int preEnd,
                                     int[] inOrder,  int inStart,  int inEnd ) {
        if(preStart > preEnd || inStart > inEnd)
            return null;
        int rootIdx = -1;
        int rootVal = preOrder[preStart];
        for(int i = inStart; i <= inEnd; ++i) {
            if(inOrder[i] == rootVal) {
                rootIdx = i;
                break;
            }
        }
        if(rootIdx < 0)
            return null;
        int len = rootIdx - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left  = buildTree(preOrder, preStart+1, preStart+len,
                               inOrder,  inStart,    rootIdx-1);
        root.right = buildTree(preOrder, preStart+len+1, preEnd,
                               inOrder,  rootIdx+1,  inEnd);
        return root;
    }
}