LeetCode 题解工作台
填充每个节点的下一个右侧节点指针 II
给定一个二叉树： struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。 初始状态下，所有 next …
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们使用队列 进行层序遍历，每次遍历一层时，将当前层的节点按顺序连接起来。 时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
示例 1：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
示例 2：
输入：root = [] 输出：[]
提示：
- 树中的节点数在范围
[0, 6000]内 -100 <= Node.val <= 100
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。
解题思路
方法一：BFS
我们使用队列 进行层序遍历，每次遍历一层时，将当前层的节点按顺序连接起来。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
"""
# 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 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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you see how missing children affect the next pointer connections across levels?
- question_mark
Can you implement this without using extra memory while still connecting all nodes correctly?
- question_mark
Will you traverse the tree level by level or rely on recursion to handle next pointer assignments?
常见陷阱
外企场景- error
Forgetting to handle the end of a level, leaving the last node's next pointer incorrectly pointing to a non-null value.
- error
Assuming the tree is perfect and not handling missing children, which breaks cross-level connections.
- error
Using recursion in the wrong order (left before right), causing next pointers to reference null instead of the correct neighbor.
进阶变体
外企场景- arrow_right_alt
Populating Next Right Pointers in Each Node (perfect binary tree version) with O(1) space requirements.
- arrow_right_alt
Level Order Traversal of Binary Tree with pointers returned as linked lists per level.
- arrow_right_alt
Flatten Binary Tree to Linked List in-place, connecting nodes in pre-order with similar pointer manipulations.