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

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

一刷
题解：几乎所有关于树的求解都要利用recursion.
注意，这里找到了root在inorder内的位置之后，用left的长度推算出在preorder内右子树的位置。
并且寻找root在inorder内的位置不能用binarySearch, 因为数组不是有序的。

    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return helper(0, 0, inorder.length - 1, preorder, inorder);
        }

        public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
            if (preStart > preorder.length - 1 || inStart > inEnd) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[preStart]);
            int inIndex = 0; // Index of current root in inorder
            for (int i = inStart; i <= inEnd; i++) {
                if (inorder[i] == root.val) {
                    inIndex = i;
                }
            }
            root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
            root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
            return root;
        }
    }

二刷
与一刷思路相同

/**
 * 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) return null;
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
    
    public TreeNode buildTree(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend){
        if(pstart> pend || istart>iend) return null;
        int rootVal = preorder[pstart];
        TreeNode root = new TreeNode(rootVal);
        int index = findIndex(inorder, istart, iend, rootVal);
        root.left = buildTree(preorder, pstart + 1, index - istart + pstart, 
                             inorder, istart, index-1);
        root.right = buildTree(preorder, index - istart + pstart+1, pend,
                              inorder, index+1, iend);
        return root;
    }
    
    public int findIndex(int[] inorder, int istart, int iend, int target){
        for(int i=istart; i<=iend; i++){
            if(inorder[i] == target) return i;
        }
        return 0;
    }
}

三刷

/**
 * 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) {
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
    
    public TreeNode buildTree(int[] preorder, int plo, int phi, int[] inorder, int ilo, int ihi) {
        if(phi<plo || ihi<ilo) return null;
        TreeNode root = new TreeNode(preorder[plo]);
        //find root index
        int root_index = search(inorder, ilo, ihi, root.val);
        int left_len = root_index - ilo;
        root.left = buildTree(preorder, plo+1, left_len + plo, 
                              inorder, ilo, root_index-1);
        root.right = buildTree(preorder, left_len + plo + 1, phi,
                              inorder, root_index+1, ihi);
        return root;
        
    }
    
    private int search(int[] nums, int from, int to, int val){
        for(int i=from; i<=to; i++){
            if(nums[i] == val) return i;
        }
        return -1;
    }
    
}