🎨Now live: Try our Free AI Image Generation Feature

Intuition
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.
Approach
- 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
: - Pop the last element from the postorder list, which is the root of the current subtree. - Create a newTreeNode
with this value. - Find the index of this value in the inorder list using the dictionary. - Recursively build the right subtree (elements after the root in the inorder list). - Recursively build the left subtree (elements before the root in the inorder list). - Return the root of the constructed tree.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the tree. Each node is processed once.
Space Complexity:
O(N), to store the dictionary and the recursive call stack.
Code
C++
class Solution {
public:
TreeNode* buildTree(vector& inorder, vector& postorder) {
int idx = postorder.size() - 1;
unordered_map 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& inorder, vector& postorder, unordered_map& 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;
}
};
Python
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)
Java
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder)
{
Map 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 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;
}
}
JavaScript
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)
};