填充每个节点的下一个右侧节点指针 图解题解
这道题到底在问什么
- 树
- [1,2,3,4,5,6,7]
- 第1层
- 1 → null
- 第2层
- 2 → 3 → null
- 第3层
- 4 → 5 → 6 → 7 → null
最优解：一步一步想明白
- 3难点就在这：5 的爸爸是 2，6 的爸爸是 3，它俩是堂兄弟，不在同一个父亲下。普通遍历很难直接把它俩接起来。
- 4省空间的诀窍：用刚连好的上一层当「跑道」。顺着上一层一路向右跑，每路过一个节点 cur，就负责把它的两个孩子接进下一层。下面一帧连一根 next，慢慢看清楚。
- 5第①根连「亲兄弟」很自然。妙在第②根：cur.next 是 cur 在上一层右边的邻居，它的 left 正好就是 cur.right 右边那个堂兄弟——上一层的 next 帮我跨过了子树的墙。
- 6所有 next = 空这是 7 个节点的完美树。一开始所有 next 都是空。目标：把每层从左到右连成链。我们一帧连一根 next 指针，盯住右边面板里那条逐渐长出来的链。
- 7leftmost = 1，1.next = 空先看第 1 层——只有根 1，它右边没人，1.next 天然是空。leftmost（每层最左节点）现在指着 1，准备借第 1 层这条「跑道」去连第 2 层。
- 8cur = leftmost = 1内层 cur 从 leftmost=1 出发，沿第 1 层向右走。第 1 层只有 1 一个节点。站在 cur=1 上，我要去连它的孩子 2 和 3。
- 9① 1.left.next = 1.right第①根：把 cur 的两个亲孩子连起来——2.next = 3。绿色的 2 是被连的节点，蓝色的 3 是它指向的右邻。这是最自然的「亲兄弟相连」。
- 10② cur.next 为空 → 3.next = 空第②根：看 cur.next（1 右边的邻居）——它是空的，说明 1 是这层最后一个。所以它的右孩子 3 就是第 2 层行末：3.next = 空。第 2 层连好了：2→3→空。
- 11cur = cur.next = 空 → 本层扫完cur 沿第 1 层的 next 往右走一步：cur = cur.next = 空。第 1 层只有一个节点，本层横扫结束。第 1 层的活干完了（变绿）。
- 12leftmost 下移到 2外层 while 下沉一层：leftmost = leftmost.left = 2。蓝色的 2 是新的每层起点。关键——刚连好的 2→3 这条链，就是我接下来遍历第 2 层的「跑道」。
- 13cur = leftmost = 2内层 cur 从 leftmost=2 出发。我会沿着第 2 层那条 2→3 的跑道，一个节点一个节点往右走，每路过一个就连它的两个孩子。先处理 cur=2。
- 14① 2.left.next = 2.rightcur=2 的第①根：连亲兄弟 4.next = 5。这两个都是 2 的孩子，挨着，很自然。第 3 层的链开始长出来了。
- 15② cur.next=3 存在 → 5.next = 3.left重头戏！cur=2 的 next 是 3（上一层早连好的，蓝色）。第②根：5.next = cur.next.left = 3.left = 6。5 和 6 是堂兄弟、父母不同，但靠 2→3 这根 next 一跳就找到了 6——上一层的链帮我跨过了子树的墙。
- 162 的左右孩子都接好了cur=2 的两根 next 都连完了：4→5（亲兄弟）、5→6（借 next 跨子树）。第 3 层的链已经长到 4 → 5 → 6，只剩 7 还没接进来。
- 17cur = cur.next = 3cur 沿着第 2 层的 next 链向右走一步：cur = cur.next = 3。这就是「不用队列」的关键动作——我没存任何节点，全靠上一层的链导航前进。2 这个节点处理完了（变绿）。
- 18cur 已到 3，准备连孩子 6、7cur 现在站在 3 上，准备处理它的两个孩子 6、7。注意 3 是第 2 层最右节点（它的 next 是空），所以待会儿连完亲兄弟后，行末那一根会指向空。
- 19① 3.left.next = 3.rightcur=3 的第①根：连亲兄弟 6.next = 7。第 3 层现在已经连成 4→5→6→7，就差最后行末那一下。
- 20② cur.next 为空 → 7.next = 空第②根：cur=3 的 next 是空，说明 3 是第 2 层最后一个，它的右孩子 7 自然就是第 3 层行末：7.next = 空。第 3 层全连好了！
- 21cur = cur.next = 空 → 本层扫完cur 再沿跑道走一步：cur = cur.next = 空。第 2 层的 2、3 都横扫完了，本层结束。第 2 层整层都干完了（变绿）。
- 22leftmost 下移到 4外层再下沉：leftmost = leftmost.left = 4。可是 4 已经是叶子、没有左孩子——外层条件 while(leftmost && leftmost.left) 不成立。说明这是最后一层，下面没有节点要连了。
- 23三层 next 链全部就绪三层的 next 链全部连好：1→空、2→3→空、4→5→6→7→空。整个过程一个队列都没用——每层都靠上一层连好的链来导航，额外空间只有几个指针，O(1)。
- 26一句话记住它：每连完一层，这层就变成了遍历它自己的「导航链」；下一层全靠它来串。链替代了队列。
- 28cur=3 行末 → cur.next 空 → 取 .left 崩看这个崩溃现场：cur=3 在行末，cur.next 是空。如果不判空就写 cur.next.left，等于对空指针取 .left，直接崩。正确做法是先 if(cur.next) 守一道，行末的右孩子 7 就让它 next 留空。
- 295.next 错连成 4 的同父 → 漏掉 65 右边明明是 6，可 6 不在 2 的子树里。只盯着自己父亲找，永远找不到 6。必须借 cur(=2) 的 next(=3)，用 3.left = 6 跨过去。记住：跨子树的连接全靠上一层的 next。
⚠️ 容易写错的地方
✗ 错：内层用 leftmost 横扫
✓ 对：用 cur 横扫，leftmost 只负责每层起点
leftmost 要留着下沉到下一层；用它横扫会丢掉起点，下一层没法开始。
✗ 错：5.next 写成 5 父亲的 right
✓ 对：写成 cur.next.left（借上一层的 next）
5 右边是堂兄弟 6，父母不同，必须靠上一层 2→3 的 next 才能跳到 6。
✗ 错：cur.next 不判空就取 .left
✓ 对：先 if (cur.next) 再连第②根
行末节点 cur.next 是空，直接取 .left 会空指针崩溃；行末右孩子本就该指向空。
✗ 错：外层条件写 while(leftmost)
✓ 对：写 while(leftmost && leftmost.left)
到最后一层叶子没有左孩子，再连会空指针；有左孩子才说明下面还有一层要连。
完整代码（Python / C++ / Java）
Python
# 节点含 left/right/next；Python 无需另外定义
class Solution:
def connect(self, root):
leftmost = root
while leftmost and leftmost.left: # 还有下一层
cur = leftmost # 沿当前层向右走
while cur:
cur.left.next = cur.right # ① 亲兄弟
if cur.next:
cur.right.next = cur.next.left # ② 借 next 跨子树
cur = cur.next # 沿上一层的链前进
leftmost = leftmost.left # 下沉一层
return rootC++
// 本题节点含 next 指针，需自定义 Node
struct Node {
int val;
Node *left, *right, *next;
Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
Node(int v) : val(v), left(nullptr), right(nullptr), next(nullptr) {}
};
class Solution {
public:
Node* connect(Node* root) {
Node* leftmost = root;
while (leftmost && leftmost->left) { // 还有下一层
Node* cur = leftmost; // 沿当前层向右走
while (cur) {
cur->left->next = cur->right; // ① 亲兄弟
if (cur->next)
cur->right->next = cur->next->left; // ② 跨子树
cur = cur->next; // 沿链前进
}
leftmost = leftmost->left; // 下沉一层
}
return root;
}
};Java
// 本题节点含 next 指针，需自定义 Node
class Node {
int val;
Node left;
Node right;
Node next;
Node() {}
Node(int v) { val = v; }
}
class Solution {
public Node connect(Node root) {
Node leftmost = root;
while (leftmost != null && leftmost.left != null) { // 还有下一层
Node cur = leftmost; // 沿当前层向右
while (cur != null) {
cur.left.next = cur.right; // ① 亲兄弟
if (cur.next != null)
cur.right.next = cur.next.left; // ② 跨子树
cur = cur.next; // 沿链前进
}
leftmost = leftmost.left; // 下沉一层
}
return root;
}
}复杂度
时间复杂度
O(n)
每个节点恰好被访问并连接一次，n 是节点总数。
空间复杂度（最优解）
O(1)
只用 leftmost、cur 几个指针；靠上一层连好的 next 链导航，不用队列。
对比 · BFS 队列解
O(n)
层序遍历需要队列存当前层节点，最宽一层约 n/2，额外空间 O(n)。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 填充每个节点的下一个右侧节点指针 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不用队列也能一层层遍历？+
因为处理某层时上一层 next 已全连好，沿上一层 next 向右走就等于遍历整层；这条链替代了队列「记住同层还有谁」的作用，所以额外空间 O(1)。
如果不是完美二叉树（116 的进阶版 117）怎么办？+
思路一样靠上一层 next 横扫，但下一层不再「填满」：要用一个 dummy 头 + tail 指针，遇到孩子就接到 tail.next，跳过空缺。核心仍是「上一层导航下一层」。
第②根连接为什么是 cur.next.left 而不是 cur.next.right？+
cur.right 右边紧挨的是「cur 右边邻居的左孩子」。cur.next 是 cur 的右邻居，它的 left 才是紧贴 cur.right 右侧那个；取 .right 会跳过一个节点。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 填充每个节点的下一个右侧节点指针 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。