1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inorderValueToIndexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderValueToIndexMap.put(inorder[i], i);
}
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderValueToIndexMap);
}
private TreeNode buildTree(int[] preorder, int preStartIndex, int preEndIndex, int[] inorder, int inStartIndex, int inEndIndex, Map<Integer, Integer> inorderValueToIndexMap) {
if (preStartIndex > preEndIndex) {
return null;
}
int rootValue = preorder[preStartIndex];
TreeNode root = new TreeNode(rootValue);
int inorderRootIndex = inorderValueToIndexMap.get(rootValue);
int leftTreeNodes = inorderRootIndex - inStartIndex;
root.left = buildTree(preorder, preStartIndex + 1, preStartIndex + leftTreeNodes, inorder, inStartIndex, inorderRootIndex - 1, inorderValueToIndexMap);
root.right = buildTree(preorder, preStartIndex + leftTreeNodes + 1, preEndIndex, inorder, inorderRootIndex + 1, inEndIndex, inorderValueToIndexMap);
return root;
}
}
|