京公网安备11010502063487号和上一题一样，要把每个结点的 next 指针指向右边的相邻结点，但这次的二叉树不再保证是"完美"的——任何结点都可能只有一个孩子或没有孩子。一个真实会犯的错误是照搬上一题（完美二叉树）针对性设计的写法，假设 head.left 和 head.right 必然成对存在，直接对可能是空的指针取属性，导致崩溃。本文用真实反例和 2000 组随机树验证，超过四分之一的普通二叉树会让这种写法直接崩溃，再给出正确的哨兵写法、5 种语言实现，以及逐层串接的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。和上一题一样是把每个结点的 next 指针指向右边的相邻结点，但这次的二叉树不再保证是"完美"的——任何结点都可能只有一个孩子或没有孩子。一共 5 组用例，覆盖：官方示例、空树、单结点、两结点、结构不规则的 7 结点树：
[1,2,3,4,5,null,7] → [[1], [2, 3], [4, 5, 7]] [] → [] [1] → [[1]] [1,2] → [[1], [2]] [1,2,3,null,4,5,null] → [[1], [2, 3], [4, 5]]
上一题（116 题）的 O(1) 空间写法里有一步是 head.left.next = head.right，隐含的前提是"只要 head 不是最底层，它就同时有左右两个孩子"——这在完美二叉树里总是成立。但普通二叉树完全可能出现只有左孩子没有右孩子（或者反过来）的结点，直接照搬这行代码，head.right 可能本来就是空的，再对它取 .next 就会崩溃：
输入 [1,2,3,4,5,null,7]（结点 2 只有左孩子 4，没有右孩子）\n正确写法（用哨兵逐个判断孩子是否存在） → [[1], [2, 3], [4, 5, 7]]\n陷阱写法（照搬116题，假设孩子必然成对存在） → 程序崩溃：AttributeError（对空指针取 .next）
陷阱写法执行到结点 2 时，head.left.next = head.right 把 4.next 设成了 None（因为 head.right 本来就是空的），这一步不会报错；但紧接着 head.right.next = head.next.left 对着一个本来就是 None 的 head.right 取 .next 赋值，直接崩溃。为了确认这不是个例，做了一次随机测试：
2,000 组随机二叉树（结点数 2 到 12）：\n照搬116题写法直接崩溃的有 551 组，占 27.6%
超过四分之一的随机树会直接触发崩溃——只要树里出现"只有一个孩子"的结点（这在非完美二叉树里很常见），针对完美二叉树设计的写法就不再成立。正确的做法必须对每个孩子分别判断是否存在，不能假设它们成对出现。
用一个哨兵结点 dummy 和一个 tail 指针，在遍历当前层（沿着上一层已经建好的 next 指针）的过程中，把下一层遇到的每个孩子（不管是左孩子还是右孩子，只要存在）依次接到 tail 后面——这样不管某个结点有几个孩子，下一层的链都能正确地被串起来。当前层处理完后，下一层的起点就是 dummy.next。时间 O(n)，空间 O(1)（不算递归/输出本身）。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def connect(root): node = root while node: dummy = Node(0) # 哨兵，标记下一层已经连出来的链的头 tail = dummy cur = node while cur: if cur.left: # 不能假设孩子一定存在，必须分别判断 tail.next = cur.left tail = tail.next if cur.right: tail.next = cur.right tail = tail.next cur = cur.next node = dummy.next # 下一层的起点 return root
$ python3 solution.py [1,2,3,4,5,null,7] → [[1], [2, 3], [4, 5, 7]] [] → [] [1] → [[1]] [1,2] → [[1], [2]] [1,2,3,null,4,5,null] → [[1], [2, 3], [4, 5]]
Java · 解法代码class Solution { public Node connect(Node root) { Node node = root; while (node != null) { Node dummy = new Node(0); // 哨兵，标记下一层已经连出来的链的头 Node tail = dummy; Node cur = node; while (cur != null) { if (cur.left != null) { // 不能假设孩子一定存在，必须分别判断 tail.next = cur.left; tail = tail.next; } if (cur.right != null) { tail.next = cur.right; tail = tail.next; } cur = cur.next; } node = dummy.next; // 下一层的起点 } return root; } }
$ javac -d build Main.java && java -cp build Main [1,2,3,4,5,null,7] → [[1], [2, 3], [4, 5, 7]] [] → [] [1] → [[1]] [1,2] → [[1], [2]] [1,2,3,null,4,5,null] → [[1], [2, 3], [4, 5]]
Go · 解法代码func connect(root *Node) *Node { node := root for node != nil { dummy := &Node{} // 哨兵，标记下一层已经连出来的链的头 tail := dummy cur := node for cur != nil { if cur.Left != nil { // 不能假设孩子一定存在，必须分别判断 tail.Next = cur.Left tail = tail.Next } if cur.Right != nil { tail.Next = cur.Right tail = tail.Next } cur = cur.Next } node = dummy.Next // 下一层的起点 } return root }
$ go run solution.go [1,2,3,4,5,null,7] → [[1], [2, 3], [4, 5, 7]] [] → [] [1] → [[1]] [1,2] → [[1], [2]] [1,2,3,null,4,5,null] → [[1], [2, 3], [4, 5]]
JavaScript · 解法代码function connect(root) { let node = root; while (node) { const dummy = new Node(0); // 哨兵，标记下一层已经连出来的链的头 let tail = dummy; let cur = node; while (cur) { if (cur.left) { // 不能假设孩子一定存在，必须分别判断 tail.next = cur.left; tail = tail.next; } if (cur.right) { tail.next = cur.right; tail = tail.next; } cur = cur.next; } node = dummy.next; // 下一层的起点 } return root; }
$ node run.js [1,2,3,4,5,null,7] → [[1], [2, 3], [4, 5, 7]] [] → [] [1] → [[1]] [1,2] → [[1], [2]] [1,2,3,null,4,5,null] → [[1], [2, 3], [4, 5]]
C++ · 解法代码class Solution { public: Node* connect(Node* root) { Node* node = root; while (node) { Node dummy(0); // 哨兵，标记下一层已经连出来的链的头 Node* tail = &dummy; Node* cur = node; while (cur) { if (cur->left) { // 不能假设孩子一定存在，必须分别判断 tail->next = cur->left; tail = tail->next; } if (cur->right) { tail->next = cur->right; tail = tail->next; } cur = cur->next; } node = dummy.next; // 下一层的起点 } return root; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [1,2,3,4,5,null,7] → [[1], [2, 3], [4, 5, 7]] [] → [] [1] → [[1]] [1,2] → [[1], [2]] [1,2,3,null,4,5,null] → [[1], [2, 3], [4, 5]]
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的 O(1) 空间哨兵实现另外和一个用标准 BFS 队列的版本做了随机对拍：
随机对拍 5,000 组（结点数 0 到 12 的随机二叉树），O(1) 空间哨兵版与 BFS 队列版的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [1,2,3,4,5,null,7]：处理第2层时，结点 2 只有左孩子 4（没有右孩子），结点 3 同时有左孩子 5 和右孩子 7；用哨兵 dummy 把这一层遇到的所有存在的孩子依次接起来，不管每个父结点有几个孩子。蓝色是正在处理的 cur，绿色是已经接入下一层链的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。