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[] inorder, int[] postorder) {
Map<Integer, Integer> inorderValueToIndexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderValueToIndexMap.put(inorder[i], i);
}
return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inorderValueToIndexMap);
}
private TreeNode buildTree(int[] inorder, int inStartIndex, int inEndIndex, int[] postorder, int postStartIndex, int postEndIndex, Map<Integer, Integer> inorderValueToIndexMap) {
if (inStartIndex > inEndIndex) {
return null;
}
int rootValue = postorder[postEndIndex];
int inRootIndex = inorderValueToIndexMap.get(rootValue);
int leftTreeNodes = inRootIndex - inStartIndex;
TreeNode root = new TreeNode(rootValue);
root.left = buildTree(inorder, inStartIndex, inRootIndex - 1, postorder, postStartIndex, postStartIndex + leftTreeNodes - 1, inorderValueToIndexMap);
root.right = buildTree(inorder, inRootIndex + 1, inEndIndex, postorder, postStartIndex + leftTreeNodes, postEndIndex - 1, inorderValueToIndexMap);
return root;
}
}
|