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

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

這種題目一看到就屬于完全無從下手的感覺室抽，答案能看懂比較好理解珊佣，但是要自己想挺難宽气。這類題應(yīng)該是題量還沒上去，還沒產(chǎn)生模糊的“這類題大概是用這種思路劳澄、方法、模版來做”的大腦反應(yīng)粒没，還需要繼續(xù)多練題多總結(jié)曲管。

Construct Tree from given Inorder and Preorder traversals

我們來看一下兩種樹的遍歷：
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

      A 
     / \
    /   \ 
 D B E   F C

We recursively follow above steps and get the following tree.

        A 
      /   \
     /     \
    B       C
   / \      / 
  /   \    /
 D     E  F

Algorithm: buildTree()

1. Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2. Create a new tree node tNode with the data as picked element.
3. Find the picked element’s index in Inorder. Let the index be inIndex.
4. Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5. Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.6) return tNode.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null){
            return null;
        }
        int len = preorder.length;
        return helper(preorder, inorder, 0,  len - 1);
    }
    
    private TreeNode helper(int[] preorder, int[] inorder, int start, int end){
        if (start > end){
            return null;
        }
        TreeNode tNode = new TreeNode(preorder[preIndex]);
        preIndex++;
        int inIndex = search(inorder, tNode.val, start, end);
        tNode.left = helper(preorder, inorder, start, inIndex - 1);
        tNode.right = helper(preorder, inorder, inIndex + 1, end);
        return tNode;
    }
    
    private int search(int[] inorder, int value, int start, int end){
        for (int i = start; i <= end; i++){
            if (inorder[i] == value){
                return i;
            }
        }
        return -1;
    }
    
    
}