117. Populating Next Right Pointers in Each Node II

Coding2023-01-296 min read

跟 116 一樣要把每個節點的 next 指向右邊的同層節點，差別是這題的樹是任意形狀，不再保證是完美二元樹。

思路

用分層 BFS 的話，這題跟 116 的程式碼完全一樣，一行都不用改。

原因是分層 BFS 從來就不依賴樹的形狀 —— 它只問「佇列裡現在有幾個節點」，那幾個就是這一層的全部。不管樹缺了多少節點、左右多不平衡，同層節點在佇列裡依然是照左到右排好的，queue[0] 依然是右邊的鄰居。

所以 116 到 117 的「升級」，對佇列解法來說是免費的。這件事本身值得記住：題目條件變寬鬆了，但解法沒有用到那個條件，所以不受影響。

（真正被影響的是 116 那個 $O (1)$ 空間的 follow-up 解 —— 它靠「左子節點的 next 一定是自己的右子節點」這種完美樹才有的結構保證，到了 117 就得改寫成「往右一路找到第一個存在的子節點」。）

分層的骨架見 102. 層序遍歷。

解題方向

"""
# 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

i < size - 1 確保每層最後一個節點的 next 維持預設的 None，不會誤串到下一層的第一個節點。

補充

這裡原本寫的是 queue.pop(0)，那會直接噴 TypeError。

TypeError: deque.pop() takes no arguments (1 given)

list.pop(0) 可以彈出最前面的元素，但 deque.pop() 不吃任何參數 —— 它固定從右邊彈出。要從左邊彈只能用 popleft()。

順帶一提，就算把 queue 改成 list 讓 pop(0) 能跑，也不該這樣寫：list.pop(0) 是 $O (n)$ （後面所有元素都要往前搬），整個 BFS 會退化成 $O (n^{2})$ 。這是 BFS 最常見的效能地雷，102 那篇也提過。

同一個骨架的家族：

題目	在那一層裡做什麼
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 是最寬那層的節點數，最壞 $O (n)$

其中 $n$ 是節點數。題目的 follow-up 一樣要求 $O (1)$ 額外空間，佇列版嚴格來說不符合，但判題會過。