树与图中等1 种解法
#116填充每个节点的下一个右侧节点指针
为完美二叉树的每个节点设置指向同层右侧相邻节点的 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, 212 - 1]范围内 -1000 <= node.val <= 1000
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
解题主线
- 固定层大小后，只连接当前层相邻节点，最后一个节点保持 null。
解法 1：BFS 逐层连接
每层维护 previous 指针，将它连接到当前出队节点。
-
时间复杂度： O(n)
-
空间复杂度： O(w)；未利用完美二叉树可达 O(1) 的额外空间性质
import java.util.*;
class Node {
int val;
Node left;
Node right;
Node next;
Node(int val) {
this.val = val;
}
}
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Deque<Node> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 每层重置前驱，防止 next 跨越层边界
Node previous = null;
// 初始 size 固定当前层范围，新入队节点留到下一轮
for (int size = queue.size(); size > 0; size--) {
Node node = queue.poll();
if (previous != null) previous.next = node;
previous = node;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
// 显式截断层尾，覆盖节点可能残留的旧 next
previous.next = null;
}
return root;
}
}边界与易错点
- 下一层节点入队不会影响当前层的连接边界。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q116_node_connect.java