Construct BT from Postorder and Inorder
Rebuild the tree from inorder and postorder traversals.
Open on LeetCode ↗02
Intuition
Mirror of the preorder version: postorder's LAST element is the root. Consume postorder from the back and build the RIGHT subtree first — the pointer then naturally hands each recursive call its root.
03
Approach
1
Root at the end
post[-1] is the root; inorder splits around it exactly as before.
2
Build right before left
Walking postorder backwards yields root, then right subtree's root, then left — so recurse right first or the pointer desynchronizes.
3
Same O(n) machinery
Value→index map, bounds instead of slices, one shared pointer.
04
Solution & live demo
python
▶1class Solution:
▶2 def buildTree(self, inorder, postorder):
▶3 idx = {v: i for i, v in enumerate(inorder)}
▶4 self.post = len(postorder) - 1
▶5 def build(lo, hi):
▶6 if lo > hi: return None
▶7 val = postorder[self.post]; self.post -= 1
▶8 node = TreeNode(val)
▶9 node.right = build(idx[val] + 1, hi) # right FIRST
▶10 node.left = build(lo, idx[val] - 1)
▶11 return node
▶12 return build(0, len(inorder) - 1)
05
Edge cases
Single node
post = in = [x] → leaf.
Left-only chain
Right recursion returns immediately at every level; pointer discipline still holds.
06
Complexity
Time
O(n)
Space
O(n)
Backward pointer, right-first recursion.