106 Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

1. Question

Given inorder and postorder traversal of a tree, construct the binary tree.

2. Implementation

(1) Recursion
1
class Solution {
2
public TreeNode buildTree(int[] inorder, int[] postorder) {
3
if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0) {
4
return null;
5
}
6
7
Map<Integer, Integer> map = new HashMap<>();
8
for (int i = 0; i < inorder.length; i++) {
9
map.put(inorder[i], i);
10
}
11
12
return constructTree(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1, map);
13
}
14
15
public TreeNode constructTree(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {
16
if (postStart > postEnd || inStart > inEnd) {
17
return null;
18
}
19
20
TreeNode root = new TreeNode(postorder[postEnd]);
21
22
int index = map.get(root.val);
23
24
root.left = constructTree(postorder, postStart, postStart + (index - inStart) - 1, inorder, inStart, index - 1, map);
25
root.right = constructTree(postorder, postStart + (index - inStart), postEnd - 1, inorder, index + 1, inEnd, map);
26
return root;
27
}
28
}
Copied!

3. Time & Space Complexity

Recursion: 时间复杂度O(n^2),如果tree是skewed, 当tree是balanced,时间复杂度是O(nlogn),空间复杂度是O(n),因为map