What is the key pattern in Populating Next Right Pointers in Each Node?

The core pattern is level-by-level pointer stitching. You treat one finished level as a linked list through next pointers, then use each parent to wire the entire level below it from left to right.

Why does the O(1) extra space solution work only because the tree is perfect?

Because every parent definitely has both left and right children, the next neighbor is always known. You never need to search ahead for an existing child, so the cross-parent connection rule stays fixed and local.

What exact links do I create for each parent node?

For every parent, first connect left child to right child. Then, if the parent has a next neighbor, connect the parent’s right child to that neighbor’s left child. Those two assignments build the next level completely.

Is BFS still acceptable for LeetCode 116?

Yes. BFS is a valid baseline and easier to describe initially, but it uses extra memory for the queue. Interviewers often expect you to notice that this problem’s perfect-tree constraint enables a cleaner constant-space pointer solution.

What is the most common failure mode in this linked-list pointer manipulation problem?

The usual mistake is solving only inside each parent and forgetting to bridge across parents. That produces correct sibling pairs like 4 to 5, but misses links like 5 to 6 between adjacent subtrees.

#116

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧…

链表树深度优先搜索广度优先搜索二叉树

题目描述

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

提示：

树中节点的数量在 [0, 2¹² - 1] 范围内
-1000 <= node.val <= 1000

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

lightbulb

解题思路

方法一：BFS

使用队列进行层序遍历，每次遍历一层时，将当前层的节点按顺序连接起来。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

"""
# 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 root is None:
            return root
        q = deque([root])
        while q:
            p = None
            for _ in range(len(q)):
                node = q.popleft()
                if p:
                    p.next = node
                p = node
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return root

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you recognize that the perfect-tree structure lets you connect parent.right directly to parent.next.left without searching for a neighbor?
question_mark
Can you explain why traversing a level through next pointers replaces a BFS queue after the previous level has been connected?
question_mark
Will you distinguish between this perfect-tree problem and the harder version where missing children break the simple cross-parent link rule?

warning

常见陷阱

外企场景

error
Connecting only left.next = right and forgetting the cross-parent bridge right.next = parent.next.left, which leaves gaps between subtrees.
error
Using a generic BFS explanation only, then missing the constant-space follow-up that this perfect binary tree specifically allows.
error
Advancing to the next level incorrectly, such as moving with leftmost.next instead of leftmost.left, which breaks the vertical progression.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Populating Next Right Pointers in Each Node II, where the tree is not perfect and missing children force neighbor discovery.
arrow_right_alt
Return the level-order traversal using next pointers after wiring, proving the horizontal links are correct without reusing the original tree edges.
arrow_right_alt
Set previous-left pointers instead of next-right pointers, reversing the same level-linking idea and changing traversal direction.

help

常见问题

外企场景

继续练习

#117 填充每个节点的下一个右侧节点指针 II #114 二叉树展开为链表 #112 路径总和