京公网安备11010502063487号给定一棵完美二叉树（每一层都填满），把每个结点的 next 指针指向它右边的相邻结点。O(1) 空间的标准做法是利用上一层已经建好的 next 指针遍历当前层，对每个结点做两件事：连接它自己的左右孩子，以及把它的右孩子和下一个兄弟的左孩子连起来。一个容易漏掉的陷阱是只做第一件事，漏了跨父结点边界的第二步连接——这会导致 next 链在两个父结点之间断裂，而且这个断裂会一层层放大。本文用真实反例证明这个错误，给出正确写法、5 种语言实现，以及双指针推进的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一棵完美二叉树（每一层都填满），把每个结点的 next 指针指向它右边的相邻结点，同一层最右边的结点 next 指向 null。一共 4 组用例，覆盖单结点、3 结点、7 结点、15 结点的完美二叉树：
[1] → [[1]] [1, 2, 3] → [[1], [2, 3]] [1, 2, 3, 4, 5, 6, 7] → [[1], [2, 3], [4, 5, 6, 7]] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → [[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]
O(1) 额外空间的标准做法是：利用上一层已经建好的 next 指针去遍历上一层，顺便把下一层连起来。对当前层的每个结点 head，要做两件事：把它自己的左右孩子连起来（head.left.next = head.right），以及把它的右孩子和"下一个兄弟结点的左孩子"连起来（head.right.next = head.next.left）——后面这一步是容易漏掉的，因为它连接的是两个不同父结点之间的边界，很容易被误以为"只要把每个父结点自己的左右孩子连好就行了"：
输入 [1,2,3,4,5,6,7]（7 结点完美二叉树）\n正确写法（连接同父孩子 + 跨父边界） → [[1], [2, 3], [4, 5, 6, 7]]\n陷阱写法（只连接同父孩子） → [[1], [2, 3], [4, 5]]
陷阱写法里，结点 5 和结点 6 之间本该连上（它们分别是结点 2 和结点 3 的右孩子），但因为跳过了跨父结点的连接，这条边没有建立——从第三层最左边的 4 开始顺着 next 走，走到 5 就断了，6 和 7 虽然仍然挂在树上，但通过 next 链已经"找不到"了。更严重的是，这个断裂会一层层放大，因为外层循环 leftmost = leftmost.left 找下一层起点没问题，但内层 while head 只能沿着（已经不完整的）next 链走，断点之后的结点根本不会被访问到，它们自己的孩子也就永远不会被连接：
规模 vs 陷阱写法在最后一层通过 next 链实际能访问到的结点数：\ndepth=1 n= 1 期望=1 实际=1\ndepth=2 n= 3 期望=2 实际=2\ndepth=3 n= 7 期望=4 实际=2\ndepth=4 n=15 期望=8 实际=2\ndepth=5 n=31 期望=16 实际=2
从第三层开始，不管树多深，陷阱写法在最底层永远只能连上 2 个结点——因为断点发生在第二层就已经限制死了后面能被正确处理的"head"数量，深度越深，"丢失"的结点比例反而越接近 100%。
外层用 leftmost 记录每一层最左边的结点（用来定位下一层从哪里开始）；内层用 head 沿着上一层已经建好的 next 指针遍历这一层的每个结点，对每个 head 做两件事：连接它自己的左右孩子，以及（如果 head.next 存在）把它的右孩子和下一个兄弟的左孩子连起来。因为全程只用了几个指针变量，没有借助队列或数组，空间是 O(1)（不算递归/输出本身）。时间 O(n)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 4 个测试用例。
Python · 解法代码def connect(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 root
$ python3 solution.py [1] → [[1]] [1, 2, 3] → [[1], [2, 3]] [1, 2, 3, 4, 5, 6, 7] → [[1], [2, 3], [4, 5, 6, 7]] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → [[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]
Java · 解法代码class 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; } }
$ javac -d build Main.java && java -cp build Main [1] → [[1]] [1, 2, 3] → [[1], [2, 3]] [1, 2, 3, 4, 5, 6, 7] → [[1], [2, 3], [4, 5, 6, 7]] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → [[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]
Go · 解法代码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 }
$ go run solution.go [1] → [[1]] [1, 2, 3] → [[1], [2, 3]] [1, 2, 3, 4, 5, 6, 7] → [[1], [2, 3], [4, 5, 6, 7]] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → [[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]
JavaScript · 解法代码function connect(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; }
$ node run.js [1] → [[1]] [1, 2, 3] → [[1], [2, 3]] [1, 2, 3, 4, 5, 6, 7] → [[1], [2, 3], [4, 5, 6, 7]] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → [[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]
C++ · 解法代码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; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [1] → [[1]] [1, 2, 3] → [[1], [2, 3]] [1, 2, 3, 4, 5, 6, 7] → [[1], [2, 3], [4, 5, 6, 7]] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] → [[1], [2, 3], [4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15]]
共 4 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 4/4\n Java 通过 4/4\n Go 通过 4/4\n JavaScript 通过 4/4\n C++ 通过 4/4
Python 版本的 O(1) 空间双指针实现另外和一个用标准 BFS 队列（每层内部按普通顺序连 next）的版本做了随机对拍：
随机对拍 2,000 组（深度 1 到 6 的完美二叉树），O(1) 空间双指针版与 BFS 队列版的结果全部一致，0 处不一致。
另外四种语言只在上面 4 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例（7 结点完美二叉树）：利用上一层已经建好的 next 指针遍历这一层，对每个 head 先连接它自己的左右孩子，再检查 head.next 是否存在，存在就把 head 的右孩子和下一个兄弟的左孩子连起来——这一步正是陷阱写法漏掉的地方。蓝色是正在处理的 head，绿色是这一层已经连好 next 的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。