116. 填充每个节点的下一个右侧节点指针
题目描述
输入一棵完美二叉树：所有叶子位于同一层，并且每个非叶子节点都恰好有两个孩子。每个节点除了 val、left、right，还有一个 next 指针，初始时全部为空。
让每个节点的 next 指向同一层中紧挨在它右边的节点。若它已经是这一层最右边的节点，next 保持为空。返回修改后的根节点。
输出采用如下序列化方式：从每层最左节点出发，沿 next 依次写出节点值，每层结束后写一个 "#"。空树输出 []。
示例 1
输入：root = [1,2,3,4,5,6,7] 输出：[1,"#",2,3,"#",4,5,6,7,"#"]
解释：三层分别连成 1、2 -> 3、4 -> 5 -> 6 -> 7，每层末尾用 "#" 隔开。
示例 2
输入：root = [] 输出：[]
解释：空树没有节点。
数据范围
- 节点总数在
[0, 2^12 - 1]之间。 -1000 <= node.val <= 1000
进阶：只用常数级别的额外空间。递归调用占用的栈空间不计入额外空间。
解题思路：利用已建 next 指针
把已经连好的一层当成链表来用。leftmost 指向每层最左节点；head 沿着这一层的 next 向右走，顺手给下一层连线：head.left.next = head.right（同一个父亲的两个孩子）；如果 head 右边还有节点，head.right.next = head.next.left（跨父亲的两个相邻孩子）。这一层走完，下一层就全连好了，leftmost 下移一层继续。
为什么正确
处理 leftmost 所在层时，这一层的 next 已经全部连好，可以像链表一样从左到右遍历；下一层的 next 正在被逐对连好。
复杂度分析
时间 O(n)：每个节点作为 head 访问一次；空间 O(1)，只用 leftmost 和 head 两个指针，不需要队列。
易错点
跨父亲那一条线最容易漏：5 和 6 的父亲不同，必须靠上一层已经连好的 head.next 才能找到 6。另外要先判断 head.next 是否为空，最右边的父亲没有右邻居。循环条件写 leftmost.left 而不是 leftmost，否则会在叶子层访问 None.left。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def connect(self, root):
leftmost = root
while leftmost and leftmost.left:
head = leftmost
while head:
head.left.next = head.right
if head.next:
head.right.next = head.next.left
head = head.next
leftmost = leftmost.left
return rootclass Solution {
public Node connect(Node root) {
Node leftmost = root;
while (leftmost != null && leftmost.left != null) {
Node head = leftmost;
while (head != null) {
head.left.next = head.right;
if (head.next != null)
head.right.next = head.next.left;
head = head.next;
}
leftmost = leftmost.left;
}
return root;
}
}class Solution {
public:
Node* connect(Node* root) {
Node* leftmost = root;
while (leftmost && leftmost->left) {
Node* head = leftmost;
while (head) {
head->left->next = head->right;
if (head->next)
head->right->next = head->next->left;
head = head->next;
}
leftmost = leftmost->left;
}
return root;
}
};func connect(root *Node) *Node {
leftmost := root
for leftmost != nil && leftmost.Left != nil {
head := leftmost
for head != nil {
head.Left.Next = head.Right
if head.Next != nil {
head.Right.Next = head.Next.Left
}
head = head.Next
}
leftmost = leftmost.Left
}
return root
}var connect = function(root) {
let leftmost = root;
while (leftmost && leftmost.left) {
let head = leftmost;
while (head) {
head.left.next = head.right;
if (head.next)
head.right.next = head.next.left;
head = head.next;
}
leftmost = leftmost.left;
}
return root;
};function connect(root: _Node | null): _Node | null {
let leftmost = root;
while (leftmost && leftmost.left) {
let head: _Node | null = leftmost;
while (head) {
head.left!.next = head.right;
if (head.next)
head.right!.next = head.next.left;
head = head.next;
}
leftmost = leftmost.left;
}
return root;
};其他解法
层序遍历通用但要 O(n) 队列；主解法把上一层已建好的 next 链当作队列用，额外空间 O(1)。
解法 2：层序遍历 时间 O(n)，空间 O(n)
用队列做广度优先搜索，每轮先记下当前层的节点数。按从左到右的顺序取出本层节点，把上一个节点 prev 的 next 指向当前节点。同时把孩子加入队列，供下一轮使用。
不依赖完美二叉树的性质，对任意二叉树都适用。队列最多存放一层节点，最底层约有 n/2 个，不满足题目常数空间的进阶要求。
from collections import deque
class Solution:
def connect(self, root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
prev = None
for _ in range(size):
node = q.popleft()
if prev:
prev.next = node
prev = node
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return rootclass Solution {
public Node connect(Node root) {
if (root == null) return root;
Deque<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
Node prev = null;
for (int i = 0; i < size; i++) {
Node node = q.poll();
if (prev != null) prev.next = node;
prev = node;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
return root;
}
}class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
Node* prev = nullptr;
for (int i = 0; i < size; i++) {
Node* node = q.front();
q.pop();
if (prev) prev->next = node;
prev = node;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return root;
}
};func connect(root *Node) *Node {
if root == nil {
return root
}
q := []*Node{root}
for len(q) > 0 {
size := len(q)
var prev *Node
for i := 0; i < size; i++ {
node := q[i]
if prev != nil {
prev.Next = node
}
prev = node
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
q = q[size:]
}
return root
}var connect = function(root) {
if (!root) return root;
let q = [root];
while (q.length) {
const next = [];
let prev = null;
for (const node of q) {
if (prev) prev.next = node;
prev = node;
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
q = next;
}
return root;
};function connect(root: _Node | null): _Node | null {
if (!root) return root;
let q: _Node[] = [root];
while (q.length) {
const next: _Node[] = [];
let prev: _Node | null = null;
for (const node of q) {
if (prev) prev.next = node;
prev = node;
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
q = next;
}
return root;
}