LeetCode 117. 填充每个节点的下一个右侧节点指针 II
目录
题目描述
题意分析
给定一棵二叉树，每个节点除了
left、right还多一个next字段，初始全是null。要求把每个节点的next指向同一层中紧挨着它右边的那个节点；一层最右边的节点没有右邻，next保持null。返回值仍是原来的根，实质是原地改指针而不是造新结构。关键约束信号在题目编号的「II」上：本题的树是普通二叉树，不再是完美二叉树。这一个字的差别决定了 116 的写法在这里全部失效。在完美二叉树里，任何非叶节点都同时有左右孩子，于是可以用两条固定关系一次搞定——同一父节点下
node.left.next = node.right，跨父节点则node.right.next = node.next.left。而这里节点可能只有左孩子、只有右孩子或者没有孩子，node.next.left很可能是null，右邻节点也许要沿着node.next.next.next找很远才出现，甚至根本不存在。换句话说，「右邻是谁」不再是一个可以从局部结构算出来的常量，必须靠扫描当层才能确定。第二个信号在进阶要求：只能使用常量级额外空间，递归产生的隐式栈空间不计入。这条把「开一个队列做层序遍历，每层把相邻节点串起来」这个最自然的写法排除在满分答案之外——它正确，但队列在最宽一层要装 $O(n)$ 个节点。既然不许额外容器，就只能从树自身已经有的指针里找可用的遍历通道。
边界情形：树为空时直接返回
null；只有根节点时什么都不用连；某一层可能只有一个节点（比如整棵树退化成一条左斜链），这一层的next应当保持null；某个节点只有右孩子没有左孩子（如[1, null, 2]），不能因为左孩子为空就跳过整个节点；next字段初始就是null，最右节点不需要显式赋值。节点数最多 6000，深度不受额外限制。
解法：利用已建立的 next 链逐层连接
核心思路
队列层序遍历很直观，但最宽一层需要 $O(n)$ 额外空间。题目要求常数空间，可以反过来利用正在构建的
next指针：上一层的next链已经连好后，它本身就是遍历这一层的通道。每轮沿当前层的
next从左到右扫描，把遇到的左孩子、右孩子依次接到下一层链表。用哑节点dummy统一处理下一层的第一个节点，tail始终指向下一层已经连接好的最后一个节点。循环不变量是：每轮开始时，
levelStart指向当前层最左节点，且当前层的next已完整建立。按父节点从左到右、每个父节点先左后右地追加孩子，得到的正好是下一层从左到右的顺序。扫描结束后令levelStart = dummy.next，不变量继续成立。这套写法不依赖完美二叉树：某个孩子不存在时直接跳过即可，跨父节点的相邻孩子仍由同一条
tail链自然连接。
解题步骤
- 用
levelStart指向当前层最左节点，初始为root。- 为下一层创建哑节点，并令
tail = dummy。- 沿当前层的
next链移动node。- 若左孩子存在就接到
tail后，再处理右孩子；每次连接后更新tail。- 当前层扫描完后，
dummy.next就是下一层最左节点，赋给levelStart。levelStart == null时结束并返回原根节点。对
[1,2,3,4,5,null,7]，第二层先得到2 -> 3；扫描它时依次追加4、5、7，因此跨父节点的5.next会正确指向7。
代码实现
class Solution {
public Node connect(Node root) {
for (Node levelStart = root; levelStart != null; ) {
Node dummy = new Node(0);
Node tail = dummy;
for (Node node = levelStart; node != null; node = node.next) {
if (node.left != null) {
tail.next = node.left;
tail = tail.next;
}
if (node.right != null) {
tail.next = node.right;
tail = tail.next;
}
}
levelStart = dummy.next;
}
return root;
}
}
func connect(root *Node) *Node {
for levelStart := root; levelStart != nil; {
dummy := &Node{}
tail := dummy
for node := levelStart; node != nil; node = node.Next {
if node.Left != nil {
tail.Next = node.Left
tail = tail.Next
}
if node.Right != nil {
tail.Next = node.Right
tail = tail.Next
}
}
levelStart = dummy.Next
}
return root
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点只在所属层被扫描一次。
- 空间复杂度：$O(1)$，只使用哑节点和若干指针；没有队列或递归栈。
关键点总结
- 用上一层已经生成的
next链代替 BFS 队列，是常数空间的关键。dummy + tail消除了“下一层第一个节点”的特殊分支。- 当前层按从左到右扫描，每个父节点按左、右孩子追加，天然保持层序。
- 与 116 不同，本题不是完美二叉树，不能使用固定的左右孩子连接公式。
易错点总结
- 把两个孩子判断写成
if / else，会在左右孩子都存在时漏掉右孩子。- 先追加右孩子再追加左孩子，会颠倒同一父节点下的顺序。
- 每层必须重新创建
dummy；复用旧哑节点会残留上一层链表。- 外层下一轮应从
dummy.next开始，而不是从levelStart.next开始。- 直接套用 116 的
node.next.left，在右邻节点缺少左孩子时会断链。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 116. 填充每个节点的下一个右侧节点指针 | 中等 | 完美二叉树版，右邻可由 node.right.next = node.next.left 直接算出，本题正是它去掉「完美」假设后的推广 |
| 102. 二叉树的层序遍历 | 中等 | 层序的模板题，要求按层分组输出，队列写法里「本层还剩几个」的计数是核心 |
| 199. 二叉树的右视图 | 中等 | 只要每层最后一个节点，本题连好 next 后沿链走到末尾即可，两题可互相印证 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 层内方向逐层翻转，考的是层边界与输出顺序的解耦 |
| 107. 二叉树的层序遍历 II | 中等 | 自底向上输出，本质是层序结果的逆序，适合练习结果收集的时机 |
| 515. 在每个树行中找最大值 | 中等 | 层内聚合而非层内连接，模板与本题的外层循环完全一致 |
| 662. 二叉树最大宽度 | 中等 | 同样按层处理，但要给节点编号来计算含空位的宽度，注意编号溢出 |
| 429. N 叉树的层序遍历 | 中等 | 孩子从两个变成任意多个，本题的两个 if 相应换成一层 for 循环 |
| 114. 二叉树展开为链表 | 中等 | 同为原地改指针把树摊成链，但顺序是前序而非层序，可用 Morris 式的常数空间做法 |