/*
* 105. Construct Binary Tree from Inorder and preorder Traversal
* 11.20 By Mingyang
* 千万不要以为root一定在中间那个点,还是要找一下中间点的位置
* p.left = construct(preorder, preStart + 1, preStart + (k - inStart),inorder, inStart, k - 1);
* p.right = construct(preorder, preStart + (k - inStart) + 1, preEnd,inorder, k + 1, inEnd);
* 难点就在于如何找到这两个起点和终点的index
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preEnd = preorder.length - 1;
int inEnd = inorder.length - 1;
return construct(preorder, 0, preEnd, inorder, 0, inEnd);
}
public TreeNode construct(int[] preorder, int preStart, int preEnd,int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int val = preorder[preStart];
TreeNode p = new TreeNode(val);
// find parent element index from inorder
int k = 0;
for (int i = 0; i < inorder.length; i++) {
if (val == inorder[i]) {
k = i;
break;
}
}
p.left = construct(preorder, preStart + 1, preStart + (k - inStart),inorder, inStart, k - 1);
p.right = construct(preorder, preStart + (k - inStart) + 1, preEnd,inorder, k + 1, inEnd);
return p;
}