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
30
31
32
| class Solution {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
Map<Integer, Integer> postValueToIndexMap = new HashMap<>();
for (int i = 0; i < postorder.length; i++) {
postValueToIndexMap.put(postorder[i], i);
}
return constructFromPrePost(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1, postValueToIndexMap);
}
private TreeNode constructFromPrePost(int[] preorder, int preStartIndex, int preEndIndex, int[] postorder, int postStartIndex, int postEndIndex, Map<Integer, Integer> postValueToIndexMap) {
if (preStartIndex > preEndIndex) {
return null;
}
TreeNode root = new TreeNode(preorder[preStartIndex]);
if (preStartIndex == preEndIndex) {
return root;
}
int leftRootValue = preorder[preStartIndex + 1];
int postLeftRootIndex = postValueToIndexMap.get(leftRootValue);
int leftTreeNodes = postLeftRootIndex - postStartIndex + 1;
root.left = constructFromPrePost(preorder, preStartIndex + 1, preStartIndex + leftTreeNodes, postorder, postStartIndex, postLeftRootIndex, postValueToIndexMap);
root.right = constructFromPrePost(preorder, preStartIndex + leftTreeNodes + 1, preEndIndex, postorder, postLeftRootIndex + 1, postEndIndex - 1, postValueToIndexMap);
return root;
}
}
|