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

# 116. Populating Next Right Pointers in Each Node

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

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

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

## 思路

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

所以骨架照抄 [102. 層序遍歷](/interview/coding/102-binary-tree-level-order-traversal)，把「收集整層」換成「把每個節點指向佇列裡的下一個」。

### 關鍵是 `queue[0]`

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

```text
處理第 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](/interview/coding/117-populating-next-right-pointers-in-each-node-ii)（任意二元樹）。

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

## 解題方向

```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: '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」變成「還沒到最後一個」：

```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

```

第二版少了 `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](/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 / [117](/interview/coding/117-populating-next-right-pointers-in-each-node-ii) | **用 `next` 串起同層節點** |

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

## 複雜度

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

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