空间解法剖析)
LeetCode 116 这题，“填充每个节点的下一个右侧节点指针”，题目本身不长，看起来最直观的做法就是层序遍历，一层层把下一个节点接起来。不过真正让这道题成为经典的不是“能不能做出来”，而是你能不能摆脱队列，做到题目那种“只能用常量级额外空间”的约束。我见过不少人第一次写这题时，队列版本能快速过掉，但一旦被追问“能不能不用队列”，整个现场就开始卡壳。
这篇内容会从题目最容易忽略的前提条件说起，先给出队列版的标准解法，再拆解空间 O(1) 的“搭桥”思路，最后聊到递归和 117 题的变体。无论你是刚开始刷二叉树，还是准备面试前想把这类题一次性吃透，都可以直接按顺序看下来。
1. 先读透题面：“完美二叉树”其实是一把钥匙
1.1 题目到底让我们填什么
题目给的二叉树定义包含四个字段：
class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {} Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} };其中next指针初始都是nullptr。你需要做的是把每个节点的next指向它同一层右侧的相邻节点。如果右边没有节点，就保持nullptr。
举个最典型的例子：
1 / \ 2 3 / \ / \ 4 5 6 7填充之后就变成：
1 -> nullptr / \ 2 -> 3 -> nullptr / \ / \ 4->5->6->7 -> nullptr注意，节点5并不是节点2的左孩子，也不是节点3的孩子，它和节点6之间没有共同的父节点，但它们同属一层，所以要通过next串起来。
1.2 “完美二叉树”这句话为什么决定了你的解法方向
题目第一句话就会强调：给定一棵完美二叉树。完美二叉树意味着什么？一句话概括就是：所有内部节点都有两个孩子，并且所有叶子节点都在同一深度。
这个条件远比它看起来重要。它意味着：只要一个节点存在，它的左右孩子一定都存在。换句话说，你在代码里遇到某个非叶子节点时，不需要判断left和right是否为nullptr，可以直接放心去访问。
这也是为什么这题可以做到常数空间，而 117 题“填充每个节点的下一个右侧节点指针 II”没那么容易。在 117 题里，树可能是任意形态的二叉树，节点可能只有一个孩子，甚至一个孩子都没有，那套只依赖满二叉树几何性质的代码就会失效。
刷树相关的题，第一反应往往不是马上写代码，而是先把树具备的约束条件在脑子里过一遍。LeetCode 116给了一个很宽松的约束，这种约束往往会在进阶追问里变成突破口。
2. 先交一份“大路边”的答案：队列版层序遍历
2.1 层序遍历的天然直觉
看到“下一节点右侧”，正常人第一反应都是层序遍历：从左到右遍历这一层时，把当前节点接到下一个要访问的节点上，不就可以了吗？
用队列层序遍历时，队列里只保存当前层的节点。在外面套一层for循环，循环的次数就是当前层的节点数。这样当处理到当前层第i个节点时，队列首部剩下的那个节点，恰好就是同一层右边那个邻居。
这也是很多人的标准答案：
class Solution { public: Node* connect(Node* root) { if (root == nullptr) return root; queue<Node*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); for (int i = 0; i < levelSize; ++i) { Node* cur = q.front(); q.pop(); if (i < levelSize - 1) { cur->next = q.front(); } if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } } return root; } };这段代码的核心只有一处：if (i < levelSize - 1) cur->next = q.front();，因为弹出当前节点后，队列首部正好是下一轮要访问的同层节点。
2.2 为什么这版只能算入门写法，不是面试官最想看到的
队列版代码很容易理解，但它的空间复杂度是O(n)。最坏情况下，完美二叉树的最后一层大约有n / 2个节点，这一整层都会放进队列里。
LeetCode 原题一开始就给出了一个看起来不起眼、实际很苛刻的限制：只能使用常数级别的额外空间。很多同学刷题时直接无视了这句话，把队列版提交上去也能 AC，但如果这是面试现场，面试官接下来很可能会追问：
你这个解法空间复杂度多少？能不能不用队列？
如果你没有准备过下一步，现场就会很被动。所以这份答案可以帮你对题，但不能帮你过面试。
另外还有个细节值得说明：这版代码没有任何leftmost、next指针之外的特殊技巧，它其实是解决 117 题的一个可用基础。因为层序遍历本身并不依赖“完美二叉树”这个前提，任何二叉树都能这样连。
3. 真正的进阶：上一层的 next，把当前层“串”起来
3.1 从“已经连好的上一层”借力
你要连接第i层的节点，其实不需要专门用一个队列把这一层存下来。因为当你在处理第i层时，第i - 1层的节点链表已经全部连接好了，你可以从第i - 1层的最左边节点出发，顺着next指针一个节点一个节点地往右走。
每走到一个上层节点，它的左右孩子都在当前层，而且这两个孩子之间必然相邻，所以直接让左孩子的next指向右孩子。真正的跨父节点连接，是右孩子去连“当前节点的next节点的左孩子”。
这样说可能有点绕，直接看规则：
- 如果
cur->left存在，那么cur->left->next = cur->right； - 如果
cur->next不为空，那么cur->right->next = cur->next->left。
第一行处理同一个父节点下的两个孩子；第二行处理跨越父节点的相邻关系。因为树是完美二叉树，所以cur->next如果有值，它必然存在左孩子，而且这个左孩子正是cur右孩子的右侧邻居。
3.2 用代码把上面的规则固化下来
看这段空间复杂度 O(1) 的迭代解法：
class Solution { public: Node* connect(Node* root) { if (root == nullptr) return root; Node* leftmost = root; while (leftmost->left != nullptr) { Node* head = leftmost; while (head != nullptr) { head->left->next = head->right; if (head->next != nullptr) { head->right->next = head->next->left; } head = head->next; } leftmost = leftmost->left; } return root; } };这段代码有两个循环，分得很清楚：
while (leftmost->left)：说明当前层下面还有一层需要连接。如果走到叶子层，没有左孩子，整棵树连接完毕，直接返回。while (head)：遍历当前已经连好的那一层。因为这一层是通过next串起来的，所以可以用head = head->next线性往后走。
外层循环结束时做leftmost = leftmost->left，这个赋值也很有讲究。leftmost一开始指向根节点，它的左孩子是第二层最左边的节点。经过内层循环后，第二层已经被连成链表了，接下来只需要跳到第二层最左端，继续去连接第三层。
3.3 手动模拟一遍，确保不是死记代码
以这棵树为例：
1 / \ 2 3 / \ / \ 4 5 6 7第一次外层循环时，leftmost = root = 1，内层head从 1 开始：
head = 1：1->left是 2，1->right是 3，执行2->next = 3；由于head->next为空，跳过第二行。head = 1->next，也就是nullptr，内层结束。
此时第二层的2和3已经连好。然后执行leftmost = leftmost->left = 2。
第二次外层循环时，leftmost = 2，内层head从 2 开始，并且借助第一轮建立的2->next，可以一路走到 3：
head = 2：2->left是 4，2->right是 5，执行4->next = 5；head->next = 3存在，执行5->next = 3->left = 6。head = 3：3->left是 6，3->right是 7，执行6->next = 7；head->next为空，跳过第二行。head = nullptr，内层结束。
此时第三层的4 -> 5 -> 6 -> 7全部连好。最后leftmost = leftmost->left = 4，进入第三次外层循环时发现4->left为空，退出。
整个过程不申请任何队列，只靠几个指针变量移动，空间自然是 O(1)。
3.4 三个容易写错的细节，现场太容易踩
第一是外层循环的判定。如果你写成while (leftmost != nullptr)，那么处理到叶子层进入循环后，内层会去访问head->left，但叶子没有孩子，可能导致逻辑错误。用leftmost->left判断更安全，直接说明还有“下一层”需要连。
第二是内层循环的推进方式。你可能会想用head = head->next->next一次跳两步。不要这样做。如果我用当前节点的左右孩子之间的关系去跳跃，看起来像是以“父节点对”为步长，但代码里head->next本身就是同层链表，逐步往前才是自然写法。一次跳两步很容易在复杂边界里翻车，而且没有收益。
第三是左右子树顺序和next是否使用冲突。内层连接第三层时，必须确保第二层已经连好。我们的代码在同一轮外层循环里先连好第二层和第三层？你有没有发现一个问题：第一次外层循环时，我们通过 head=1 连接了 2->3，同时这个内层循环也把 4、5、6、7 串起来了吗？并没有。因为连接第三层依赖第二层的next，第一次外层循环时，第二层才刚刚被连成链表，还没有被遍历到；真正去连接第三层，发生在第二层已经是“上一层”之后。
所以整体的处理节奏是：每一轮外层循环负责“利用已连接的上一层，连接它的下一层”。第一次外层循环连接第二层，第二次外层循环连接第三层。这种错位感是这道题最难想通的地方。
4. 递归版思路：连接自己的左右孩子，剩下的交给下一层
4.1 递归版的直接直觉
还有一个很自然的解法是递归。对于每个节点来说，它只需要做两件事：把自己的左右孩子连起来，然后如果它自己有右侧邻居，就让右孩子去连邻居的左孩子。整体上递归地处理左子树和右子树。
代码如下：
class Solution { public: Node* connect(Node* root) { if (root == nullptr) return root; if (root->left != nullptr) { root->left->next = root->right; } if (root->right != nullptr && root->next != nullptr) { root->right->next = root->next->left; } connect(root->left); connect(root->right); return root; } };核心逻辑是，任意一个节点，例如节点2：
- 节点
2的左孩子是 4，右孩子是 5，所以 4 连 5。 - 节点
2的右侧邻居是 3，而节点 3 的左孩子是 6，所以 5 连 6。
这里的root->right->next = root->next->left就是跨父节点的连接，也是整个递归里最“精华”的一行。
4.2 为什么递归不用额外维护当前层的队列
因为递归栈天然帮我们保留了“回到上一层”的途径。当我们处理完根节点，递归进入左子树时，左子树的根节点，也就是节点 2，它的next已经被根节点设置好了。这样节点 5 需要连到节点 6 的时候，可以直接通过节点 2 的next找到节点 3。
换句话说，上层的next关系是先从根节点开始向下传播的，每一层递归函数的入口都保证当前节点已经拿到了它需要的右侧邻居信息。
需要注意递归函数内部的顺序：必须先处理当前节点的孩子连接，再递归左右子树。如果先把connect(root->left)放前面，左子树递归执行时节点 2 的next还没有被设置，整棵左子树里的跨父节点连接就会出错。
4.3 递归的空间复杂度到底算不算 O(1)
官方题解里说“递归可以，默认递归栈不计算额外空间”，所以很多刷题讨论直接说递归版空间是 O(1)。
实际面试中如果面试官很较真，你可以说明清楚：递归过程使用了调用栈，对于完美二叉树来说树高是O(log n)，严格意义下递归栈的空间不是常数。只是因为题目允许“忽略隐式栈空间”，所以递归解法可以作为可接受答案。
真正想强调的空间 O(1) 方案，还是第 3 节那种迭代写法。两者在思路上各有价值：迭代版更接近面试官想要的“常数空间”，递归版更直观、更容易口头解释。
4.4 这个递归思路为什么不太能直接搬到 117 题
117 题的目标是把任意二叉树的next指针连起来。如果树的形态不保证是完美二叉树，像root->left或者root->right可能为空，这时候你没法直接写root->left->next = root->right。
更难处理的是跨父节点的连接。比如当前节点的右孩子为空，那它右侧的邻居可能是当前节点next的某个左孩子，也可能是next节点本身，甚至可能是再往后隔了好几个节点的某个子节点。你需要从root->next开始不断向右找第一个带有孩子的节点。
所以 117 题的常用思路会和 116 有较大差异，这也是为什么我单独用一节来讲变体。
5. 从 116 延展到 117：当“完美”前提消失后要改哪里
5.1 117 题里最常见的高效做法：哑节点串层法
117 题给的是普通二叉树。仍然可以用队列层序遍历完成，但如果要在常数空间下完成，就不能依赖父节点的“必然双孩子”关系。更通用的做法是维护一个哑节点，用它作为下一层链表的头，然后把遍历当前层时遇到的非空子节点依次接到链表后面。
参考代码可以这样写：
class Solution { public: Node* connect(Node* root) { Node* cur = root; while (cur != nullptr) { Node dummy; Node* tail = &dummy; for (Node* p = cur; p != nullptr; p = p->next) { if (p->left != nullptr) { tail->next = p->left; tail = tail->next; } if (p->right != nullptr) { tail->next = p->right; tail = tail->next; } } cur = dummy.next; } return root; } };这段代码里，dummy是每一层用来临时挂链表的头。遍历当前层时，把每个节点非空的左孩子和右孩子依次往后接。等当前层遍历完，dummy.next就是下一层的第一个节点，于是cur = dummy.next进入下一轮。
这个思路能处理 117 题的核心原因，是它不再假设每个父节点都有两个非空孩子，而是在遍历时动态收集非空节点。每层只用一个哑节点和尾指针，空间仍然是 O(1)。
5.2 对照 116 和 117，看清“不同前提导致的不同解法”
可以简单对比一下：
| 对比项 | 116 题 | 117 题 |
|---|---|---|
| 树结构 | 完美二叉树 | 任意二叉树 |
| 左孩子是否存在 | 有父节点就一定有 | 不一定 |
| 右孩子是否一定存在 | 有父节点就一定有 | 不一定 |
| 能否直接使用“当前节点左右孩子相邻” | 能 | 不能 |
| 典型 O(1) 思路 | 借助上层已连接的链表 | 每层收集非空子节点组成新链表 |
| 递归版是否适合 | 很适合 | 稍复杂，需要额外寻找右侧可用节点 |
如果你在面试中被问到 116，紧接着又被 117 追问差异，对比到这个颗粒度，基本已经展示出你对树的形态敏感度了。
5.3 面试官常在这样的题上设置哪些追问
面试官最常问的切入点有几个。第一问解法，你给出层序遍历；第二问如何做到 O(1)；第三问开始延伸到变体，比如“如果树不是满的怎么办”“如果树的深度特别大到递归栈会爆怎么办”。
最后这个问题很容易被忽略。116 题因为树是完美二叉树，高度是O(log n)，递归栈通常不会爆；但 117 题如果给出一棵极端的链状树，递归深度可以达到n，递归就存在栈溢出风险。这也是为什么 117 题更推荐迭代解法。
一旦你在思考逻辑中加入了“树形会影响递归深度”的意识，面试官就很容易确认你不是在死记硬背题库，而是真正理解结构特征对算法选择的影响。
6. 刷题手记：边界处理、模板记忆法与现场复盘
6.1 边界条件每次都该检查哪几个
这类题边界不算多，但一定要动手测一遍，不能只看理论。
第一个边界是空树root = nullptr。迭代版和递归版都要在最前面直接返回root。你的代码如果能把空树挡住，后面所有逻辑都安全。
第二个边界是只有一个节点的树。进入迭代版的外层循环时，leftmost->left是 null，循环不会执行，直接返回。这一个用例能帮你在心理上确认循环条件写对了。
第三个边界是只有两层的完美二叉树。它需要连接第二层的唯一两个节点，然后再进入叶子层时退出。这是一个非常适合断点调试的小用例。
// 手动构造一个两层的完美二叉树 Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); // 调用后检查 root->left->next == root->right6.2 代码模板别硬背，理解递进关系才不容易忘
如果你把这题反复刷了几遍，可以按下面这个顺序来记忆：
- 最普通的解法是队列 BFS，能用但空间 O(n)。
- 想要 O(1)，必须意识到：上一层一旦连好，它就是下一层的“遍历载体”。
- 连接方式无非两种：同父孩子直接连，跨父节点借助当前节点的 next 去连。
- 外层循环从最左节点往下走，内层循环顺着当前层节点往右走。
这一套思路不仅适用于 116，还能帮助你快速定位 117 里哑节点法的来源：116 是通过“父节点关系”直接知道下一层怎么串；117 的形态不确定，就主动遍历当前层，把遇到的所有非空子节点串成新链表。两种解法其实是同一个思想在不同约束条件下的自然延伸。
6.3 一道题可以延伸出的其他练习方向
刷完 116 和 117 之后，建议顺便做两个附加练习：
第一，把 116 的迭代版改成 Python 版本，不要看参考答案，直接靠理解重写。这样可以检验你是否清楚每个指针的走向。
第二，考虑“如果树的深度很大，递归版会不会爆栈”这个问题，你可以动手构造一条超长链式树，然后实际跑一下 Java 或 C++ 的递归版，观察栈溢出现象。这个实验比只看文档更能加深记忆。
根据我自己的刷题经验，碰到next指针相关题目，最值得养成的习惯是先分清两层概念：当前层和下一层。代码里所有交换、赋值、跳转，只要你能在脑子里清晰标注当前变量停在“哪一层的第几个节点”，基本就不会错乱。反过来，如果你盯着指针链总是绕晕，大概率是因为没把“上一层”和“下一层”的职责分开。116 题最好的练习方式，就是把它当作一堂堂空间复杂度优化课来过，而不是只把它归类成一道普通 BFS 题。
