从前序与中序遍历序列构造二叉树

class TreeNode {

int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
    val = x;
}

}

public class Solution {

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int preLen = preorder.length;
    int inLen = inorder.length;
    if (preLen != inLen) {
        throw new RuntimeException("Incorrect input data.");
    }
    return buildTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
}

private TreeNode buildTree(int[] preorder, int preLeft, int preRight,
                           int[] inorder, int inLeft, int inRight) {
    // 因为是递归调用的方法，按照国际惯例，先写递归终止条件
    if (preLeft > preRight || inLeft > inRight) {
        return null;
    }
    // 先序遍历的起点元素很重要
    int pivot = preorder[preLeft];
    TreeNode root = new TreeNode(pivot);
    int pivotIndex = inLeft;
    // 严格上说还要做数组下标是否越界的判断 pivotIndex < inRight
    while (inorder[pivotIndex] != pivot) {
        pivotIndex++;
    }
    root.left = buildTree(preorder, preLeft + 1, pivotIndex - inLeft + preLeft,
            inorder, inLeft, pivotIndex - 1);
    root.right = buildTree(preorder, pivotIndex - inLeft + preLeft + 1, preRight,
            inorder, pivotIndex + 1, inRight);
    return root;
}

}