Why it works
- Postorder ends with the root, and in inorder the root stands between its left and right subtrees: one look-up in pos splits the range into the two subtrees.
- Read from the end, postorder is node, right subtree, left subtree. So the right side is built first: then next, moving only backwards, always points at the root of the range being built.
- Each half is the same problem on a smaller range, so the same function builds it; an empty range is an empty subtree.
Complexity
Time O(n): every value becomes a node once, and pos finds its place in O(1). Memory O(n): pos holds every value, and the call stack is as deep as the tree is tall.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗