Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
题意：给出一个二叉树的前序和中序遍历结果，并且这个二叉树中没有重复值，复原这个二叉树。
思路：
复原一个二叉树的第一步是要找到根节点，而前序遍历的第一个值就是根节点的值。
找到根节点以后，下一步是复原根节点的左子树和右子树。因为二叉树中没有重复值，所以在中序遍历中找和根节点值相同的位置，这个位置左边都是左子树中的点，右边都是右子树的点。
知道了左右子树各自节点的个数，再回到前序遍历，就也能确定左右子树的根节点的位置了，最后就是递归的复原左右子树了。
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart >= preorder.length || inStart > inEnd) {
return null;
}
TreeNode parent = new TreeNode(preorder[preStart]);
int inIndex = inStart;
for (int i = inStart; i <= inEnd; i++) {
if (preorder[preStart] == inorder[i]) {
inIndex = i;
break;
}
}
parent.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
parent.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return parent;
}