1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
return null;
}
return helper(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
}
private TreeNode helper(int[] inorder, int s1, int e1, int[] preorder, int s2, int e2) {
if (s1 > e1 || s2 > e2) {
return null;
}
TreeNode root = new TreeNode(preorder[s2]);
int k = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == root.val) {
k = i;
break;
}
}
root.left = helper(inorder, s1, k - 1, preorder, s2 + 1, s2 + k - s1);
root.right = helper(inorder, k + 1, e1, preorder, s2 + k - s1 + 1, e2);
return root;
}
}
|