117. Populating Next Right Pointers in Each Node II
This is the follow-up to Populating Next Right Pointers in Each Node — same wiring job, but the safety net is gone: the tree is now an arbitrary binary tree, so any node may be missing one or both children.
Each node carries an extra pointer named next that starts out empty. Your function receives the root and must set every node's next to the node immediately to its right on the same level, even when that neighbor lives in a completely different subtree several gaps away. The last node of each level keeps next = None. Return the root when done.
The queue solution from part I still works untouched. The real challenge: keep it O(1) extra space when you can no longer count on both children existing.
Example 1:
Input: root = [1, 2, 3, 4, 5, null, 7]
Output: [1, #, 2, 3, #, 4, 5, 7, #]
Explanation: Node 3 has no left child, so 5's next must jump across the gap to 7. Each # marks the end of a level, where next is None.
Example 2:
Input: root = [1]
Output: [1, #]
Explanation: A lone root is its own level; its next stays None.
Constraints:
- 1 ≤ number of nodes ≤ 6000
- -1000 ≤ Node.val ≤ 1000
Hints:
The level-order queue approach from part I never assumed the tree was perfect — drain each level while linking the previously popped node to the current one, and it just works here.
For O(1) space, treat the level you already wired as a linked list. Walk it with a parent pointer while growing the child level behind a dummy head and a tail pointer: every child you meet (left or right, whichever exists) gets appended via tail.next. When the parent walk ends, dummy.next is the leftmost node of the next level.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, 5, null, 7]
Expected output: [1, #, 2, 3, #, 4, 5, 7, #]