Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
題意：給出一個二叉樹的前序和中序遍歷結(jié)果厢拭，并且這個二叉樹中沒有重復(fù)值俏蛮，復(fù)原這個二叉樹同廉。
思路：
復(fù)原一個二叉樹的第一步是要找到根節(jié)點，而前序遍歷的第一個值就是根節(jié)點的值典鸡。
找到根節(jié)點以后寞酿，下一步是復(fù)原根節(jié)點的左子樹和右子樹邢疙。因為二叉樹中沒有重復(fù)值，所以在中序遍歷中找和根節(jié)點值相同的位置檬嘀，這個位置左邊都是左子樹中的點，右邊都是右子樹的點责嚷。
知道了左右子樹各自節(jié)點的個數(shù)鸳兽，再回到前序遍歷，就也能確定左右子樹的根節(jié)點的位置了罕拂，最后就是遞歸的復(fù)原左右子樹了揍异。
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;
}