Why it works
- Preorder starts 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.
- Preorder lists the whole left subtree before the right one, so building left first takes the values exactly in preorder: next only moves forward.
- 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 ↗