输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
首先先上一个结论，根据前序遍历和后序遍历无法确定一个二叉树(可以用两个节点的二叉树验证)，前序遍历和中序遍历、后序遍历和中序遍历这两种是可以确定二叉树的。
前序遍历的第一个节点1是根节点，因为节点不含重复的数字，所以我们在中序遍历中查找此值，这样 4,7,2是左子树的，5,3,8,6是右子树的。前序遍历中的2,4,7是属于左子树，3,5,6,8是属于右子树的。
这样一遍下来我们搞定了一个根节点，接下来递归的处理左子树和右子树即可(写的这么简略是因为我也不知道该怎么更详细的解释)。
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
TreeNode node = constructCore(pre, in, 0, pre.length - 1, 0, pre.length - 1);
return node;
}
private TreeNode constructCore(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
int root = pre[preStart];
TreeNode node = new TreeNode(root);
if (preStart == preEnd) {
return node;
}
int pos = indexOf(in, root);
int leftTreeLength = pos - preStart; //左子树的节点数量
int rightTreeLength = preEnd - pos; //右子树的节点数量
if (leftTreeLength > 0) {
node.left = constructCore(pre, in, preStart + 1, preStart + leftTreeLength, inStart, pos - 1);
}
if (rightTreeLength > 0) {
node.right = constructCore(pre, in, preStart + leftTreeLength + 1, preEnd, pos + 1, inEnd);
}
return node;
}
private int indexOf(int[] arr, int target) {
if (arr == null || arr.length < 1) {
return -1;
}
for (int i = 0; i < arr.length; i++) {
if (target == arr[i]) {
return i;
}
}
return -1;
}
