116. Populating Next Right Pointers in Each Node

──────────────────────────────────────────────────────────────────────

116. Populating Next Right Pointers in Each Node

給一棵完美二元樹（每一層都填滿），把每個節點的 next 指向它右邊的同層節點；每層最右邊那個指向 None。

這一題要考的點是進行 BFS 時，是否可以按照樹的層級來遍歷。

思路

只要能分層，這題就結束了 —— 因為 next 要串的就是「同一層裡相鄰的兩個節點」，而分層 BFS 的佇列裡，同層節點本來就是照左到右排好的。

所以骨架照抄 102. 層序遍歷，把「收集整層」換成「把每個節點指向佇列裡的下一個」。

關鍵是 queue[0]

彈出一個節點之後，佇列最前面那個就是它右邊的鄰居 —— 只要兩個都還在同一層裡。

處理第 2 層，佇列 = [B, C]

popleft() → B      此時 queue[0] 是 C     B.next = C
popleft() → C      C 是這層最後一個        C.next = None

所以唯一要小心的是每層最後一個節點：它彈出後 queue[0] 會是下一層的第一個節點，串過去就錯了。用 i 和 size 判斷「我是不是這層最後一個」即可。

「完美二元樹」這個條件用不到

題目強調樹是完美的，但分層 BFS 根本不在乎樹長什麼形狀 —— 佇列裡有幾個就處理幾個。所以同一份程式碼原封不動就能解 117. Populating Next Right Pointers II（任意二元樹）。

「完美」這個條件只有在挑戰題目的 follow-up（$O(1)$ 額外空間）時才有意義，那時候可以靠「左子節點的 next 一定是自己的右子節點」這種結構保證來省掉佇列。

解題方向

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        
        if not root:
            return root
        
        queue = deque([root])
        
        while queue:
            size = len(queue)
            while size > 0:
                node = queue.popleft()
                if size == 1:
                    node.next = None
                else:
                    node.next = queue[0]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                size -= 1
        
        return root
                

這版用 size 倒數，size == 1 就代表現在處理的是這層最後一個。

換成 for i in range(size) 會更貼近 102 的骨架，判斷條件也從「倒數到 1」變成「還沒到最後一個」：

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':

        if not root:
            return root

        queue = deque([root])

        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i < size - 1:
                    node.next = queue[0]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return root

第二版少了 else: node.next = None 那一段，因為 next 的預設值本來就是 None —— 最後一個節點不去動它就對了。這也讓「只在需要時才寫入」這件事更清楚。

補充

佇列版嚴格來說不符合題目的 follow-up。 題目寫的是「You may only use constant extra space」，而佇列會用到 $O(w)$。LeetCode 判題會過，但那個 follow-up 才是這題真正想考的：利用上一層已經串好的 next，把它當成一條鏈結串列來走，就能在不開佇列的情況下建好下一層。我沒有用這個角度寫過，但知道那是這題的完整解。

跟 117 的關係：117 把「完美二元樹」的條件拿掉，但這份 BFS 程式碼不用改任何一行。

同一個骨架的家族：

題目	在那一層裡做什麼
102. Level Order	收集整層
199. Right Side View	只取最後一個
515. Largest Value in Each Row	取 max
1302. Deepest Leaves Sum	求和，只留最後一層
103. Zigzag Level Order	奇數層反轉
116 / 117	用 next 串起同層節點

整理見 Tree 遍歷模板。

複雜度

• 時間 $O(n)$ — 每個節點進出佇列各一次
• 空間 $O(w)$ — w 是最寬那層的節點數；完美二元樹的最後一層剛好是 $(n+1)/2$，所以是 $O(n)$

其中 $n$ 是節點數。follow-up 的解法可以做到 $O(1)$。