[LeetCode每日一题]105. Construct Binary Tree from Preorder and Inorder Traversal

题目如下：

Given preorder and inorder traversal of a tree, construct the binary tree.
eg:
    preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]
    return:
      3
     / \
    9  20
    /    \
  15      7

已知二叉树的前序遍历序列和中序遍历序列，让我们写出二叉树的结构。 如所给例子所示，首先取前序遍历序列preorder中的第一个元素3，则在中序遍历序列中[9]是3的左子树，[15,20,7]是3的右子树。再看preorder，20是[20,15,7]的根，再看inorder，15是20的左子树，7是20的右子树。 代码实现如下：

/**
 * 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) {
        return buildTree(0, 0, preorder.length - 1, preorder, inorder);
    }

    public TreeNode buildTree(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart >= preorder.length || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int rootIndex = inStart;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] != preorder[preStart]) {
                continue;
            }
            rootIndex = i;
            break;
        }
        TreeNode left = buildTree(preStart + 1, inStart, rootIndex - 1, preorder, inorder);
        TreeNode right = buildTree(preStart + (rootIndex - inStart) + 1, rootIndex + 1, inEnd, preorder, inorder);
        root.left = left;
        root.right = right;
        return root;
    }
}