填充每个节点的下一个右侧节点指针

难点就在这：5 的爸爸是 2，6 的爸爸是 3，它俩是堂兄弟，不在同一个父亲下。普通遍历很难直接把它俩接起来。

省空间的诀窍：用刚连好的上一层当「跑道」。顺着上一层一路向右跑，每路过一个节点 cur，就负责把它的两个孩子接进下一层。下面一帧连一根 next，慢慢看清楚。

第①根连「亲兄弟」很自然。妙在第②根：cur.next 是 cur 在上一层右边的邻居，它的 left 正好就是 cur.right 右边那个堂兄弟——上一层的 next 帮我跨过了子树的墙。

完美树 · 初始：这是 7 个节点的完美树。一开始所有 next 都是空。目标：把每层从左到右连成链。我们一帧连一根 next 指针，盯住右边面板里那条逐渐长出来的链。

第1层 · 根 1 无右邻：先看第 1 层——只有根 1，它右边没人，1.next 天然是空。leftmost（每层最左节点）现在指着 1，准备借第 1 层这条「跑道」去连第 2 层。

cur = 1 · 站上跑道：内层 cur 从 leftmost=1 出发，沿第 1 层向右走。第 1 层只有 1 一个节点。站在 cur=1 上，我要去连它的孩子 2 和 3。

连第1根 next · 2 → 3：第①根：把 cur 的两个亲孩子连起来——2.next = 3。绿色的 2 是被连的节点，蓝色的 3 是它指向的右邻。这是最自然的「亲兄弟相连」。

cur=1 是行末 · 3 → 空：第②根：看 cur.next（1 右边的邻居）——它是空的，说明 1 是这层最后一个。所以它的右孩子 3 就是第 2 层行末：3.next = 空。第 2 层连好了：2→3→空。

cur 沿跑道前进 · cur = 1.next：cur 沿第 1 层的 next 往右走一步：cur = cur.next = 空。第 1 层只有一个节点，本层横扫结束。第 1 层的活干完了（变绿）。

下沉一层 · leftmost = leftmost.left = 2：外层 while 下沉一层：leftmost = leftmost.left = 2。蓝色的 2 是新的每层起点。关键——刚连好的 2→3 这条链，就是我接下来遍历第 2 层的「跑道」。

cur = 2 · 站上第2层跑道：内层 cur 从 leftmost=2 出发。我会沿着第 2 层那条 2→3 的跑道，一个节点一个节点往右走，每路过一个就连它的两个孩子。先处理 cur=2。

连一根 next · 4 → 5：cur=2 的第①根：连亲兄弟 4.next = 5。这两个都是 2 的孩子，挨着，很自然。第 3 层的链开始长出来了。

借 next 跨子树 · 5 → 6：重头戏！cur=2 的 next 是 3（上一层早连好的，蓝色）。第②根：5.next = cur.next.left = 3.left = 6。5 和 6 是堂兄弟、父母不同，但靠 2→3 这根 next 一跳就找到了 6——上一层的链帮我跨过了子树的墙。

cur=2 两根连完 · 第3层长出 4→5→6：cur=2 的两根 next 都连完了：4→5（亲兄弟）、5→6（借 next 跨子树）。第 3 层的链已经长到 4 → 5 → 6，只剩 7 还没接进来。

cur 沿跑道前进 · cur = 2.next = 3：cur 沿着第 2 层的 next 链向右走一步：cur = cur.next = 3。这就是「不用队列」的关键动作——我没存任何节点，全靠上一层的链导航前进。2 这个节点处理完了（变绿）。

cur = 3 · 站上节点 3：cur 现在站在 3 上，准备处理它的两个孩子 6、7。注意 3 是第 2 层最右节点（它的 next 是空），所以待会儿连完亲兄弟后，行末那一根会指向空。

连一根 next · 6 → 7：cur=3 的第①根：连亲兄弟 6.next = 7。第 3 层现在已经连成 4→5→6→7，就差最后行末那一下。

cur=3 是行末 · 7 → 空：第②根：cur=3 的 next 是空，说明 3 是第 2 层最后一个，它的右孩子 7 自然就是第 3 层行末：7.next = 空。第 3 层全连好了！

cur 沿跑道前进 · cur = 3.next：cur 再沿跑道走一步：cur = cur.next = 空。第 2 层的 2、3 都横扫完了，本层结束。第 2 层整层都干完了（变绿）。

下沉一层 · leftmost = leftmost.left = 4：外层再下沉：leftmost = leftmost.left = 4。可是 4 已经是叶子、没有左孩子——外层条件 while(leftmost && leftmost.left) 不成立。说明这是最后一层，下面没有节点要连了。

循环结束 · 全部连好：三层的 next 链全部连好：1→空、2→3→空、4→5→6→7→空。整个过程一个队列都没用——每层都靠上一层连好的链来导航，额外空间只有几个指针，O(1)。

一句话记住它：每连完一层，这层就变成了遍历它自己的「导航链」；下一层全靠它来串。链替代了队列。

易错实演 · 忘判空就崩：看这个崩溃现场：cur=3 在行末，cur.next 是空。如果不判空就写 cur.next.left，等于对空指针取 .left，直接崩。正确做法是先 if(cur.next) 守一道，行末的右孩子 7 就让它 next 留空。

易错实演 · 跨子树连错：5 右边明明是 6，可 6 不在 2 的子树里。只盯着自己父亲找，永远找不到 6。必须借 cur(=2) 的 next(=3)，用 3.left = 6 跨过去。记住：跨子树的连接全靠上一层的 next。

三个边界：空树和单节点都因为没有下一层而直接返回；每层最右节点的 next 由 if 守卫天然保证指向空，不用特判。

面试常追问三点：为什么省得掉队列、不是完美树怎么改（117）、第②根为什么取 .left。把「上一层导航下一层」这条主线讲清就稳了。