Why it works
- The stack holds the path from the root down to cur, like the calls of the recursive walk. A node leaves it only once both of its subtrees are in out.
- A node reaches the top of the stack twice when it has a right child: before its right subtree and after it. last is the node that went to out just before, so node.right is last means we are coming back.
- Without last, the second time would go right again and loop forever.
Complexity
Time O(n): every node is pushed and popped once, and seen on top at most twice. Memory O(h), where h is the height of the tree: the stack holds one path from the root down.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗