LeetCode 116这道题我前前后后刷过好几遍每次重写都有新体会。题目本身不难但它非常典型给定一棵完美二叉树要求把每个节点的 next 指针指向同一层右侧的节点如果右侧没有节点就保持 NULL。很多人第一反应是层序遍历用一个队列逐层连起来但这道题的进阶要求是只用额外常数空间完成这时候就需要换个思路。这篇文章我会从最直观的层序遍历讲起再一步步引导到递归解法和真正的 O(1) 空间迭代解法最后把我在调试中踩过的坑整理出来。适合刚接触二叉树、准备算法面试、或者已经刷过一些题但想把同层连接这类问题彻底吃透的读者。1. 整体设计与思路拆解1.1 先看题完美二叉树和 next 指针题目给出的二叉树节点长这样class Node: def __init__(self, val: int 0, left: Node None, right: Node None, next: Node None): self.val val self.left left self.right right self.next next和普通二叉树节点相比多了一个 next 指针。初始状态下所有节点的 next 都是 NULL。我们需要把每层节点从左到右用 next 串起来最后一个节点的 next 继续保持 NULL。题目明确说了是“完美二叉树”这意味着所有叶子节点都在同一层并且每个内部节点都有两个子节点。这个条件非常关键它保证每一层都是满的不会出现缺左缺右的情况。很多人一开始容易把 next 和 right 混淆其实 next 是横向的层内链表指针right 是纵向的二叉树子节点指针二者完全不同。还有一个容易被忽略的点题目示例里给的是完全填充后的效果也就是说从根节点出发沿着 next 可以走完一整层。最终结构可以理解成每一层都是一条单链表而 next 就是链表节点的 next。1.2 为什么说思路选型是这道题的核心如果只追求“能做出来”层序遍历是最快的方案用一个队列逐层弹出节点按顺序连接即可。但面试官大概率会追问一句“能不能不用额外空间”一旦问到这就说明这道题真正的考点不在层序遍历而在“如何利用已经构造好的 next 指针作为下一层的跳板”。我在面试中遇到过类似的追问候选人如果能从 BFS 平滑过渡到常数空间解法通常会被认为对数据结构理解更扎实。你不需要一上来就写最优解但最好展示出你知道不同方案的取舍。比如先说“最直接的是层序遍历时间 O(N)空间 O(N)”再补一句“但如果要求 O(1) 空间可以换成利用 next 指针逐层下移的做法”面试官就会觉得你心里有完整地图。还有一点值得说这类题考察的不只是二叉树遍历更是一种“把树看成链表”的抽象能力。116 题做到位之后再去做 LeetCode 117填充普通二叉树每个节点的下一个右侧节点指针思路会顺很多。2. 最直观的层序遍历解法2.1 用队列保存一层的节点层序遍历是最容易想到的方向。BFS 天然就是一层一层扫只需要在处理每一层的时候把该层节点从左到右用 next 连起来即可。实现时需要用队列记录节点并且在每一层开始前记录当前层的节点数 size。为什么要记 size因为如果不记队列里会混入下一层的节点你就不知道当前层从哪里结束。记下 size 之后只弹出 size 个节点剩下的自然留到下一轮处理。我推荐一个清晰写法用一个 prev 变量记录前一个弹出的节点每弹出一个新节点就让 prev.next 指向它再更新 prev 为当前节点。这样写比queue[0]那种依赖队列内部状态的写法更直白面试时也更不容易出错。from collections import deque def connect(root: Node) - Node: if not root: return root q deque([root]) while q: prev None for _ in range(len(q)): node q.popleft() if prev: prev.next node prev node if node.left: q.append(node.left) if node.right: q.append(node.right) return root注意每一层开始时把 prev 重置为 None这样每层最左侧节点的 next 不会被误连接到上一层的尾巴上。等 for 循环跑完当前层prev 会停在该层最右侧节点它的 next 也没有被额外赋值所以保持 NULL满足题意。2.2 复杂度分析和一个小陷阱时间复杂度是 O(N)因为每个节点恰好进队列一次、出队列一次。空间复杂度最坏 O(N)因为在完美二叉树中最后一层大约有 N/2 个节点队列会在处理倒数第二层时把这些节点全部装下。这个解法在 LeetCode 上可以直接通过但如果面试官追问“能否不用队列”就需要进入下一关了。这里有个小陷阱有些人在写 BFS 时会尝试用两个队列交替存储当前层和下一层也能实现但空间复杂度同样是 O(N)并没有本质提升。更关键的是这种写法代码冗长还容易在切换队列时搞混指针。如果你只是刷题BFS 版本可以当作保底方案如果你在准备面试我建议把重心放到后面的 O(1) 空间解法上。3. 常数空间的递归解法3.1 递归怎么借用上一层指针递归解法属于从 BFS 到最优解之间的“中间答案”。它的核心在于不靠队列而是靠上一层已经连好的 next 指针来串联下一层。对于一个节点 root假设它已经有左右子节点。第一件要做的事很简单把左孩子的 next 指向右孩子因为这两个节点天然相邻。第二件事稍微隐蔽一些如果 root 自身有 next说明 root 右边还有同层节点那么 root 的右孩子应该指向 root.next 的左孩子。这解决的是“跨父节点”的相邻问题。比如第三层的节点 5它属于节点 2 的右子树它右边的节点 6 属于节点 3 的左子树2 和 3 是相邻的兄弟节点所以 5 必须借助 2.next 才能摸到 6。于是递归体可以这样写def connect(root: Node) - Node: if not root: return root if root.left: root.left.next root.right if root.next: root.right.next root.next.left connect(root.left) connect(root.right) return root这段代码反复处理一件事当前节点的下一层连接。等当前节点处理完再去递归左右子树层层往下推进。3.2 递归实现和踩坑点这个版本最大的坑是漏掉root.right.next root.next.left这一行。如果漏了最终结果里会出现“同一层但来自不同父节点的相邻节点之间没有连接”数据看起来一半是好的一半是断的。我调试的时候会在纸上画一棵三层的完美二叉树给每个节点编号根节点 1第二层 2、3第三层 4、5、6、7在递归到节点 2 时先连 4-5再连 5-6。这里的 5-6 就是跨父节点连接因为 6 不是 2 的直接子节点。如果没有root.next分支4-5 有了但 5-6 没有第三层就无法串成一条完整的链表。还有一个细节递归调用应该放在连接操作之后。虽然从逻辑上讲先递归再连接也不是一定错但“先连接本层再深入下层”的思路最清晰也更容易向别人解释。你可以在编写时形成固定习惯减少现场出错概率。3.3 递归空间不是严格 O(1)这里必须说清楚递归解法虽然不用显式队列但系统调用栈会占用空间递归深度等于树的高度 O(log N)。所以如果严格按“常量级额外空间”衡量递归版本并不满足。不过 LeetCode 官方 Follow up 里说“递归深度不计入额外空间”所以很多题解会把它当成一种可接受解法。但面试时如果面试官较真你最好主动指出这一点然后说“我可以改成迭代写法把空间压到 O(1)”。这既能展示你对复杂度的理解也能自然引出下一版代码。4. 真正的 O(1) 迭代实现4.1 核心思想每一层都是一条现成的链表递归解法已经比较接近最优但还有系统栈开销。迭代解法完全不用栈也不需要队列只靠几个变量就能完成全部连接。核心思想是当我们在第 k 层时这一层的节点已经通过上一轮的连接从 leftmost 开始沿着 next 串成了一条链表。我们顺着这条链表走同时为第 k1 层建立 next 连接。等走完当前层再把 leftmost 下沉到下一层的最左侧节点重复这个过程。因为题目保证是完美二叉树所以当前层的每个节点都有左孩子和右孩子。于是连接下一层只有两种场景同一个父节点的左右孩子直接相连head.left.next head.right相邻父节点的右孩子和左孩子跨树相连head.right.next head.next.left第二种场景需要head.next存在如果不存在说明当前节点已经是本层最右侧节点它的右孩子就是下一层最右侧节点不需要再往后连。4.2 代码与逐行拆解来看完整代码def connect(root: Node) - Node: if not root: return root leftmost root while leftmost.left: head leftmost while head: head.left.next head.right if head.next: head.right.next head.next.left head head.next leftmost leftmost.left return root这个代码很短但每一行都有意义。我建议你拿一棵三层完美二叉树把 leftmost、head 的变化一步步写出来初始 leftmost 1进入 while leftmost.left因为 1 有左孩子 2head 1处理第二层的连接2.next 31.next 不存在所以不处理 3.nexthead 变成 3但 3 没有 next第二层循环结束leftmost 下沉到 2此时 2 有左孩子 4继续循环head 2先连 4.next 52.next 3 存在所以 5.next 6head 3先连 6.next 73.next 不存在不处理 7.nexthead 变成 None循环结束leftmost 44 没有左孩子整个 while 循环退出最终得到的层级连接就是第一层1第二层2 - 3第三层4 - 5 - 6 - 7非常干净。4.3 为什么循环条件用 leftmost.left 而不是 leftmost这个细节是迭代版本最容易卡住的地方。如果写成while leftmost当 leftmost 下沉到最后一层时head 会指向叶子节点然后head.left.next就会因为head.left为 None 直接报错。用leftmost.left作为循环条件隐式利用了完美二叉树的性质只要当前层不是最后一层最左侧节点一定有左孩子一旦到了最后一层leftmost.left 为 None循环自然结束。这个条件既避免了空指针又不需要额外记录当前深度非常优雅。有些人可能会问如果树只有根节点呢此时 leftmost.left 是 None循环一次都不执行直接返回 root跟预期一致。所以边界情况也处理得很好。5. 高频问题与排查技巧实录5.1 报错NoneType has no attribute next这个错误在迭代解法里最常出现原因通常是循环条件写错进入了最后一层还想继续连接。我曾经把while leftmost.left误写成while leftmost结果 head 跑到叶子节点下一行head.left.next直接爆空指针。排查方法很简单在循环开头打印leftmost.val和当前head.val看看是不是已经进入叶子层。或者临时加一行assert head.left is not None如果断言失败就能立即定位到循环条件的问题。真实面试中你不太可能打印太多东西但在本地调试时这招特别管用。5.2 为什么右侧还有节点没连上如果代码跑完发现某一层的 next 链在中间断了最常见的原因是跨父节点连接缺失。比如递归版本里少了root.right.next root.next.left迭代版本里少了if head.next: head.right.next head.next.left。这个问题的隐蔽之处在于它不会报错只会让最终结果不符合预期。调试时我习惯在纸上画出第三层把每个节点属于哪个父节点标出来然后挨个检查 next 边是否完整。还有一个惯例性的检查点从最左侧叶子开始沿着 next 一直走看能不能走完一整层如果能走完基本就对了。5.3 死循环迭代解法里死循环通常有两个来源一是内层head head.next忘了写导致 head 永远停在当前节点二是 leftmost 下沉写错比如leftmost leftmost.left被写成了leftmost head导致 leftmost 无法进入下一层或者反复在同一层转圈。这类问题比空指针更隐蔽因为程序不会立刻崩。我的经验是加一个计数器或者打印当前节点值观察输出是否重复。如果你看到同一个数字连续出现多次基本就是指针更新逻辑出了问题。另外每写完一个循环检查循环变量是否在每次迭代都有明确的前进路径这是一个通用好习惯。5.4 问题速查表症状常见原因解决方案空指针异常循环进入叶子层leftmost 判断条件错误使用while leftmost.left而不是while leftmost层内连接断裂漏写跨父节点连接补充right.next next.left分支结果顺序错乱BFS 中没重置 prev每层开始前把 prev 设为 None死循环忘记更新 head 或 leftmost检查head head.next和leftmost leftmost.left最后一层 next 错误把叶子节点也当成有 child 的节点处理循环条件已经排除最后一层不要手动连最后一层递归空间超限树退化为链递归深度过大换成迭代解法这个表是我在实际刷题时自己总结的每次卡住先看表格能省不少时间。6. 思路扩展从 116 走向更多题6.1 如果二叉树不是完美二叉树怎么办LeetCode 117 就是同样题目的非完美版本。那里每个节点不一定都有左右孩子所以不能简单地用leftmost.left判断下一层是否存在。解决办法是用一个 dummy 节点作为下一层的虚拟头然后遍历当前层时把存在的子节点依次接到 dummy 后面。这样即使某层只有一个节点也能正确串联。建议先把 116 的迭代解法吃透再去做 117。116 的完美性质帮你屏蔽了大量边界判断让你能聚焦在“利用 next 指针串联下一层”这个核心思想上。等这个思想稳固了再去处理各种为空的情况难度会小很多。6.2 这类题真正锻炼的能力这道题看起来只是在填指针实际上是在训练你几种能力对二叉树层结构的理解、对链表串联的操作、对空间复杂度的敏感度以及在不同解法之间取舍的判断力。我见过不少候选人能写出 BFS 版本但一提到“减少空间”就卡住。这往往不是不会写代码而是没有建立“上级层可以作为下级层的索引”这种直觉。116 题恰好能补齐这块。如果你彻底搞懂了递归版和迭代版再去看类似“二叉树每层右视图”“填充每个节点的下一个右侧节点指针 II”这些题会明显轻松很多。另外这道题也提醒我刷算法题不要只看标准答案最好把不同思路都亲手写一遍。BFS、递归、迭代三个版本各有各的边界亲手踩过坑面试时才不会慌。我个人在实际刷题中的体会是先把图画出来再对着图走一遍代码比盯着屏幕硬想有效得多。尤其像 116 这种指针连接题纸笔模拟三五个节点就能把逻辑盘得清清楚楚。如果你现在正卡在某一个版本上不妨试试把整棵树的每一层 next 边都画出来再对照代码一行行走很快就会豁然开朗。这个习惯我一直保留到现在遇到链表、树相关的题目都很管用。