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; queueNode* 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 11-left是 21-right是 3执行2-next 3由于head-next为空跳过第二行。head 1-next也就是nullptr内层结束。此时第二层的2和3已经连好。然后执行leftmost leftmost-left 2。第二次外层循环时leftmost 2内层head从 2 开始并且借助第一轮建立的2-next可以一路走到 3head 22-left是 42-right是 5执行4-next 5head-next 3存在执行5-next 3-left 6。head 33-left是 63-right是 7执行6-next 7head-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是否使用冲突。内层连接第三层时必须确保第二层已经连好。我们的代码在同一轮外层循环里先连好第二层和第三层你有没有发现一个问题第一次外层循环时我们通过 head1 连接了 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 题。