---
title: "117. Populating Next Right Pointers in Each Node II"
url: "https://laigary.com/interview/coding/117-populating-next-right-pointers-in-each-node-ii"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Linked List", "Tree", "Breadth-First Search"]
---

# 117. Populating Next Right Pointers in Each Node II

[117\. Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)

跟 [116](/interview/coding/116-populating-next-right-pointers-in-each-node) 一樣要把每個節點的 `next` 指向右邊的同層節點，差別是**這題的樹是任意形狀**，不再保證是完美二元樹。

## 思路

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

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

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

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

分層的骨架見 [102. 層序遍歷](/interview/coding/102-binary-tree-level-order-traversal)。

## 解題方向

```python
"""
# 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`。**

```python
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](/interview/coding/102-binary-tree-level-order-traversal) 那篇也提過。

**同一個骨架的家族**：

| 題目 | 在那一層裡做什麼 |
|---|---|
| [102. Level Order](/interview/coding/102-binary-tree-level-order-traversal) | 收集整層 |
| [199. Right Side View](/interview/coding/199-binary-tree-right-side-view) | 只取最後一個 |
| [515. Largest Value in Each Row](/interview/coding/515-find-largest-value-in-each-tree-row) | 取 max |
| [1302. Deepest Leaves Sum](/interview/coding/1302-deepest-leaves-sum) | 求和，只留最後一層 |
| [103. Zigzag Level Order](/interview/coding/103-binary-tree-zigzag-level-order-traversal) | 奇數層反轉 |
| [116](/interview/coding/116-populating-next-right-pointers-in-each-node) / 117 | **用 `next` 串起同層節點** |

整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 每個節點進出佇列各一次
- 空間 $O(w)$ — `w` 是最寬那層的節點數，最壞 $O(n)$

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