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
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0) {
return null;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return constructTree(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1, map);
}
public TreeNode constructTree(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {
if (postStart > postEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(postorder[postEnd]);
int index = map.get(root.val);
root.left = constructTree(postorder, postStart, postStart + (index - inStart) - 1, inorder, inStart, index - 1, map);
root.right = constructTree(postorder, postStart + (index - inStart), postEnd - 1, inorder, index + 1, inEnd, map);
return root;
}
}
3. Time & Space Complexity
Recursion: 时间复杂度O(n^2),如果tree是skewed, 当tree是balanced,时间复杂度是O(nlogn),空间复杂度是O(n),因为map
Previous105 Construct Binary Tree from Preorder and Inorder TraversalNext606 Construct String from Binary Tree
Last updated
Was this helpful?