Construct BT from Postorder and Inorder
Rebuild the tree from inorder and postorder traversals.
Open on LeetCode ↗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.
Postorder read backwards gives roots in root-right-left order, so consuming it from the end means building the right subtree before the left. It's the preorder construction mirrored — the same code with the cursor moving the other way and the two recursive calls swapped.
Approach
Root at the end
post[-1] is the root; inorder splits around it exactly as before.
Build right before left
Walking postorder backwards yields root, then right subtree's root, then left — so recurse right first or the pointer desynchronizes.
Same O(n) machinery
Value→index map, bounds instead of slices, one shared pointer.
Solution & live demo
Common pitfalls
Building left before right
node.left = build(lo, idx[val] - 1) node.right = build(idx[val] + 1, hi)
node.right = build(idx[val] + 1, hi) node.left = build(lo, idx[val] - 1)
Walking postorder backwards encounters the right subtree's nodes before the left's. Building left first makes the cursor hand right-subtree values to the left branch, producing a structurally valid but completely wrong tree.
Starting the cursor at 0
self.post = 0
self.post = len(postorder) - 1
The root is the last element of postorder, not the first. Starting at the front takes a leaf as the root and the whole reconstruction collapses.
Incrementing the cursor
val = postorder[self.post]; self.post += 1
val = postorder[self.post]; self.post -= 1
The array is consumed from the end towards the front, so the cursor moves backwards. Incrementing runs off the end immediately.
Edge cases
post = in = [x] → leaf.
Right recursion returns immediately at every level; pointer discipline still holds.