NeetCode #417LC-116MediumTrees
← Back to All Problems#417 · #116 · Populating Next Right Pointers in Each Node(填充每个节点的下一个右侧节点指针)
📌 Problem Statement & Constraints
You are given a perfect binary tree where all leaves are at the same depth and every parent has two children. Each node has an extra
next pointer; populate it so each node points to the next node on the same level, with the last node of each level pointing to None. Constraints: the number of nodes is in [0, 2^12 - 1].💡 Core Algorithmic Approaches
- Process the tree level by level using the
nextpointers themselves -- no queue is needed, so the extra space is O(1). - For each level, walk the chain of parents and connect:
left.next = right, andright.next = parent.next.leftwhen the parent has a next. - The second connection is the crucial one: it links across different parents on the same level.
- Then descend via
leftmost = leftmost.left.
💻 Benchmark Python3 Implementation
class Solution:
def connect(self, root: "Optional[Node]") -> "Optional[Node]":
if not root:
return None
leftmost = root
while leftmost.left: # while there is a level below
head = leftmost
while head:
# connect the two children of this parent
head.left.next = head.right
# connect across parents on the same level
if head.next:
head.right.next = head.next.left
head = head.next # move along the current level
leftmost = leftmost.left # descend one level
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(1) extra: the level chain is traversed through the next pointers.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the cross-parent connection: without
head.right.next = head.next.left, the levels would break between subtrees. - Using a BFS queue: it works but costs O(n) space, while the pointer-based traversal needs O(1).
- Connecting
head.right.next = head.next: that links to a node on the same level but the wrong one; the target ishead.next.left. - Looping
while headwithout descending: the traversal would never reach the lower levels.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.