[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

链接：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
难度：Medium
题目：105. Construct Binary Tree from Preorder and Inorder Traversal

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

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

翻译：给定树的前序和中序遍历，构造二叉树。 注意： 树中不存在重复项。

思路：首先，你应该知道

前序遍历：根节点，左子树，右子树；
中序遍历：左子树，根节点，右子树；
所以，我们可以从preorder中找到整棵树的根节点，即为preorder[0]，由于preorder和inorder是对同一棵树的遍历，我们可以知道preorder[0]在inorder中一定也存在，不妨设preorder[0]==inorder[k]。

由于inorder是中序遍历，所以k左边的就是根节点左子树的中序遍历、k右边的就是根节点右子树的中序遍历。

并且，我们已经知道了根节点左子树的节点数（与中序遍历长度相同），不妨设为l，我们可以知道preorder从1到l+1就是根节点左子树的前序遍历，剩下的最后一部分就是根节点右子树的前序遍历。

由此，我们可以计算出左子树、右子树的前序遍历和中序遍历，从而可以用分治的思想，将规模较大的问题分解成为两个较小的问题，然后递归的进行处理，还原左子树和右子树，最后连通根节点一起组成一棵完整的树。

参考代码：
Java

/**
 * 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) {
        Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
        for(int i=0; i<inorder.length; i++)
            inorderMap.put(inorder[i],i);
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, inorderMap);
    }
    
    public TreeNode buildTree(int[] preorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight, Map<Integer,Integer> inorderMap){
        if(pLeft>pRight || iLeft>iRight)
            return null;
        TreeNode cur = new TreeNode(preorder[pLeft]);
        //int i=0;
        //for(i=iLeft; i<= iRight; i++)
        //    if(preorder[pLeft] == inorder[i])
        //        break;
        int i = inorderMap.get(preorder[pLeft]);
        
        cur.left = buildTree(preorder, pLeft+1, pLeft+i-iLeft, inorder, iLeft, i-1, inorderMap);
        cur.right = buildTree(preorder, pLeft+i-iLeft+1, pRight, inorder, i+1, iRight, inorderMap);
        return cur;
    }
}