Dare2Solve
The last element in the postorder traversal is the root of the tree. By finding this root in the inorder traversal, we can determine the boundaries of the left and right subtrees. This process can be repeated recursively for each subtree.
Use a dictionary to map each value in the inorder traversal to its index for quick lookup.
Define a recursive function build
that takes the start and end indices of the current subtree in the inorder traversal.
In each call to build
:
TreeNode
with this value.Return the root of the constructed tree.
O(N), where N is the number of nodes in the tree. Each node is processed once.
O(N), to store the dictionary and the recursive call stack.
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int idx = postorder.size() - 1;
unordered_map<int, int> map;
for (int i = 0; i < inorder.size(); ++i) {
map[inorder[i]] = i;
}
return build(inorder, postorder, map, idx, 0, inorder.size() - 1);
}
private:
TreeNode* build(vector<int>& inorder, vector<int>& postorder, unordered_map<int, int>& map, int& idx, int start, int end) {
if (start > end) return nullptr;
TreeNode* node = new TreeNode(postorder[idx--]);
node->right = build(inorder, postorder, map, idx, map[node->val] + 1, end);
node->left = build(inorder, postorder, map, idx, start, map[node->val] - 1);
return node;
}
};
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not inorder or not postorder:
return None
# Dictionary to store the index of each value in inorder traversal
idx_map = {val: idx for idx, val in enumerate(inorder)}
def build(start, end):
if start > end:
return None
# Last element in postorder is the root of current tree/subtree
root_val = postorder.pop()
root = TreeNode(root_val)
# Split the tree into left and right subtrees using the inorder index
idx = idx_map[root_val]
# Build right subtree before left subtree
root.right = build(idx + 1, end)
root.left = build(start, idx - 1)
return root
return build(0, len(inorder) - 1)
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder)
{
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(inorder, postorder, map, postorder.length - 1, 0, inorder.length - 1);
}
private TreeNode build(int[] inorder, int[] postorder, Map<Integer, Integer> map, int postIdx, int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(postorder[postIdx]);
int inIdx = map.get(postorder[postIdx]);
root.right = build(inorder, postorder, map, postIdx - 1, inIdx + 1, inEnd);
root.left = build(inorder, postorder, map, postIdx - (inEnd - inIdx) - 1, inStart, inIdx - 1);
return root;
}
}
var buildTree = function(inorder, postorder)
{
let idx = postorder.length-1
let map = {}
inorder.forEach((el, i) => map[el] = i)
function build(start, end){
if(start > end) return null
let node = new TreeNode(postorder[idx--])
node.right = build(map[node.val]+1, end)
node.left = build(start, map[node.val]-1)
return node
}
return build(0, inorder.length-1)
};