LeetCode 513这道题我的建议是每一位刷二叉树专题的人都要把它做透。题目名字叫《找树左下角的值》给定一棵二叉树返回最后一层最左边的节点值。它难度不高却在一道题里同时踩中了层序遍历、递归深度、边界处理三个考点非常适合当作二叉树知识点的总结题来对待。这篇内容不会只丢一个能过的答案我会把两种主流解法、背后的思考路径、刷题时容易踩的坑以及从这道题延伸出去的一串经典题目一次讲透。如果你正准备面试或者在系统刷LeetCode热题100和二叉树专项这篇正好对路。新手可以直接照抄代码加注释跑通有经验的也能在反向入队法递归深度控制这些细节里找到一点新东西。1. 题目到底在问什么先拆解左下角三个字1.1 一句话说清题目我给你翻译成人话一棵二叉树从上到下分了很多层你要找到最深的那一层然后在那一层里找出最靠左的节点返回它的值。题目原描述里经常出现一个词——bottom left。LeetCode 513的原题是英文的中文社区翻译过来有叫找树左下角的值也有叫最底层最左边的值都指向同一个定义。注意这个定义有两个限定条件第一必须是最后一层第二必须是这一层里最左边的节点。两个条件缺一不可。有一个隐藏性质值得多说一句二叉树的最后一层节点其实全部都是叶子节点。因为只要某个节点还有孩子那孩子所在的层一定比它更深它就不可能是最后一层的节点。所以这道题本质上就是找到最深层的那一组叶子取最左边的一个。这个性质对理解DFS解法里的叶子判断会很有用。1.2 第一层坑左下角不等于一路向左很多人看到左下角三个字第一反应是从根节点一路往左走到底不就行了。这个直觉在大部分入门二叉树文章里是被反复灌输的但放到这道题上它是错的。我举个例子1 / \ 2 3 \ 4如果按一路往左走你会得到节点2但这棵树的最后一层是深度2的那一层这一层只有一个节点4所以左下角的值应该是4不是2。问题就出在最左必须满足最深这个前提。再看一个反例1 / \ 2 3 / \ 4 5这棵树的最后一层是深度2节点4和5都在这一层左下角是4。一路往左走恰好也能到4属于碰巧。但前面那个例子已经说明没有深度信息加持的向左路径根本不能保证到达最后一层。这也是为什么这道题被很多老师拿来当知识点总结题的原因——它逼着你把层次深度最左这三个概念分开想清楚然后再缝合到一起。2. BFS层序遍历最稳的一版解法2.1 层序为什么是天然答案BFS层序遍历的逻辑是从上到下一层一层访问同一层内部按照从左到右的顺序处理。既然题目要的就是最后一层第一个节点层序遍历几乎就是照着答案写的——你只需要在遍历过程中记录每一层的第一个节点最后一层记录到的那个就是结果。如果不用显式地记录每层第一个还有一种更巧妙的做法既然我们最终要的是最后访问的那个节点那只要调整同层节点的入队顺序让每一层都从右往左遍历那么整棵树遍历过程中最后被访问到的节点天然就是最后一层最左边的节点。这就是很多题解里说的反向入队法。这两种思路一种直白一种精巧我都会给出完整实现。2.2 写法一记录每层第一个出队节点Python最常见的层序遍历版本用队列保存当前层的节点每层处理完后进入下一层。关键点在于每层循环里第一个从队列里弹出的节点就是这一层最左边的节点。from collections import deque class Solution: def findBottomLeftValue(self, root): if not root: return -1 queue deque([root]) leftmost root.val while queue: size len(queue) for i in range(size): node queue.popleft() if i 0: leftmost node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) return leftmost这里for i in range(size)里的size必须在进入循环前用len(queue)保存下来不能写成for i in range(len(queue))原因后面第4节会专门讲。leftmost变量是不断被覆盖的每处理完一层它就更新成那一层最左边的值所以循环结束时它自然就是最后一层最左边的值。这个版本比较符合直觉面试时先在白板上写这个基本不会出错。2.3 写法二反向入队法Python Java第二种写法非常飘逸也是很多官方题解喜欢用的版本。核心就一句话每次出队一个节点先把右孩子入队再把左孩子入队整个遍历顺序就会变成同一层从右往左层与层从上往下最终最后一个出队的节点就是左下角。from collections import deque class Solution: def findBottomLeftValue(self, root): queue deque([root]) node root while queue: node queue.popleft() if node.right: queue.append(node.right) if node.left: queue.append(node.left) return node.val为什么出队顺序会变成从右往左我画个最简单的例子1 / \ 2 3 / \ / \ 4 5 6 7队列初始是[1]。弹出1把右孩子3放进去再把左孩子2放进去队列变成[3, 2]。接下来弹出3放入它的右孩子7和左孩子6队列变成[2, 7, 6]。再弹出2放入5和4队列变成[7, 6, 5, 4]。你看第二层节点从右往左弹出第三层也是从右往左弹出最后一层最左边的是4它在最后才被弹出。这个版本少了一个leftmost变量逻辑更紧凑。Java版本同样简洁class Solution { public int findBottomLeftValue(TreeNode root) { QueueTreeNode queue new LinkedList(); queue.offer(root); TreeNode node root; while (!queue.isEmpty()) { node queue.poll(); if (node.right ! null) queue.offer(node.right); if (node.left ! null) queue.offer(node.left); } return node.val; } }我实测下来这个解法在LeetCode 513上时间和内存表现都很好代码也少。但有个前提你要能熟练解释为什么最后一个出队的节点就是左下角如果面试官追问而你自己都没画过例子容易被带崩。2.4 BFS的时间与空间复杂度BFS的时间复杂度是 O(n)n是二叉树节点个数因为每个节点都恰好入队出队一次。空间复杂度取决于队列在任意时刻最多能装多少节点也就是二叉树的最大宽度。最坏情况下比如一棵满二叉树最后一层节点数约 n/2所以空间复杂度最坏是 O(n)。这个复杂度水准对 LeetCode 513 的数据规模节点数最多一万多来说完全没压力。但如果你要写递归版复杂度的解释方式就完全不同了见下一节。3. DFS递归解法手动补上深度这个维度3.1 核心思路首次到达该深度的节点就是最左DFS深度优先搜索天然不带层的概念它关心的是深度。好在我们可以用递归函数的参数把深度逐层传下去然后在遍历过程中记录一个见过的最大深度。这套逻辑的关键在于一个判断每当某个节点所在的深度大于当前记录的最大深度就更新答案。因为DFS先走左子树再走右子树所以每个深度第一次被解锁的时候访问到的那个节点一定是这一层最左边的节点。之后同层的其他节点再访问到时深度不再大于已记录的最大深度也就不会覆盖答案。用生活化的类比你拿着一个本子往地下停车场一层层走每到一个新楼层第一次见到的深度就在本子上写下这一层第一个看到的车位号。之后在这一层看到其他车位一律不记。等你把整栋楼走完本子上最后一条记录就是最深一层第一个看见的车位。3.2 Python实现与逐行注释class Solution: def findBottomLeftValue(self, root): self.max_depth -1 self.answer 0 def dfs(node, depth): if not node: return # 核心判断首次到达当前深度 if depth self.max_depth: self.max_depth depth self.answer node.val # 先左后右保证同一深度优先访问最左节点 dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return self.answer这里self.max_depth初始化为 -1是因为根节点的深度是0而 -1 小于0所以根节点一定会在第一轮被记录为答案。如果你习惯让根节点深度是1那max_depth就初始化为0逻辑一模一样。self.answer会被不断覆盖只有当depth self.max_depth时才更新。整个DFS走完后answer保存的就是最深一层最左边的节点值。3.3 为什么必须先左后右如果把代码改成先递归右子树、再递归左子树会得到什么答案会变成右下角。因为每个深度第一次被访问到时是从右子树路径到达的记录的自然是这一层最右边的节点。这个顺序极其容易被忽略。我自己第一次写这个解法时凭直觉先写了dfs(node.left)再dfs(node.right)刚好对了。但后来想改成从右往左版本的题目时发现只要把两行顺序换一下就行。这说明先左后右不是代码习惯而是跟答案绑定的必要条件。如果你想在面试里展示自己对这个细节的理解可以主动跟面试官说一句这里递归顺序是关键先访问左子树保证了更新条件触发时记录的是最左节点。3.4 递归深度的边界问题DFS递归在刷题时有个隐患递归深度。Python默认递归深度上限是1000层LeetCode上二叉树的深度最坏可以到一万甚至更多。如果测试用例给了一棵链状树每个节点只有左孩子DFS递归到第1001层就会抛出RecursionError。我在实际做这道题时没有踩到递归深度的坑因为513的测试数据对DFS是友好的。但如果是自己扩展练习或者把代码搬到一个节点特别多的场景BFS迭代版本就不会有这个问题。这是面试时选择BFS的一个正当理由你不仅能给出正确的答案还能解释为什么在极端输入下BFS比DFS更稳。如果面试官坚持要你写DFS也可以给出一个补充方案显式用栈做迭代版DFS。但坦白说迭代DFS模拟递归的先序、中序、后序过程比BFS麻烦不如直接用BFS。4. 刷题现场常见的四个错误4.1 队列size提前保存的失误第一个高频错误发生在BFS写法里。新手容易写出下面这种代码while queue: for i in range(len(queue)): node queue.popleft() ...表面上看range(len(queue))在每次循环开始时计算一次长度好像没什么问题。但在Python里range的参数只在生成range对象时求值一次之后循环次数就固定了。所以这种写法其实是能用的它等于在进入for循环前把当时的len(queue)快照了下来。真正出错的是Java或C里常见的写法while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i queue.size(); i) { // 每次循环都重新取值 TreeNode node queue.poll(); ... } }这里i queue.size()会在每次循环时重新计算size而poll操作又让队列变小导致循环次数不足一层没处理完就提前进入下一层。我见过不少人在IDE里单步调试才找到这个问题。所以代码规范要统一进入循环前先把size保存到一个局部变量里循环条件用这个局部变量判断。不管什么语言这个习惯都不亏。4.2 深度变量更新时机不对DFS版本的坑主要在成员变量的更新时机。如果你把max_depth和answer作为局部变量放进递归函数就会遇到每次递归栈都是新变量的问题。比如有的人会写def dfs(node, depth): max_depth -1 answer 0 ...这样每次递归进来都会把max_depth重新初始化为-1等于什么也没记录最终返回一个错误答案。正确的做法是要么把max_depth和answer定义成类的成员变量用self.前缀要么在嵌套函数里用nonlocal声明def findBottomLeftValue(self, root): max_depth -1 answer 0 def dfs(node, depth): nonlocal max_depth, answer ...nonlocal在LeetCode的编辑器里是支持的但很多面试场景下考官更习惯看到self.max_depth这种成员变量的写法不容易产生歧义。4.3 把左下角当成了最左叶子前面第1节提过最后一层的节点全部都是叶子。但这不意味着你可以直接写找到最左的叶子。举个反例1 / 2 / 3这棵树只有一条左链最后一层的节点是3它确实是最左叶子。如果题目改成返回整棵树最左边的叶子节点不论深度答案也是3碰巧一致。但下面这棵树就不一样1 / \ 2 3 / 4最后一层是节点4左下角是4。如果按最左叶子找从根节点开始2和4是叶子最左叶子是2那就错了。所以判断左之前必须先满足深这个前提。这也是DFS版本里我把更新条件设计为depth max_depth而不是如果是叶子就更新的原因。你可以在心里记一句话这道题不是找到最左的叶子而是找到最深层的首节点。4.4 递归栈溢出与元素取值错误递归栈溢出前面已经提过。还有一个不太容易被发现的取值错误如果二叉树节点值本身可以是任意整数那不要把answer初始化为一个特定的魔法值比如-1或0因为如果根节点的值恰好等于初始值会干扰判断。比如有人写self.answer -1而整棵树的根节点值正好是-1并且最后一层左下角也是-1那答案碰巧对。可如果左下角是0但代码对DFS的更新顺序理解错了导致缓存没更新就可能返回一个听起来很合理的错误值。正确思路是answer初始值无所谓反正只要正确执行DFS它一定会在第一轮被覆盖。真正决定答案的是max_depth的比较逻辑不是answer的初始值。4.5 常见问题速查表错误现象可能原因修复方案返回结果少了一层Java遍历时循环条件没保存size先用局部变量保存queue.size()再循环DFS返回根节点的值max_depth定义在递归函数内部被反复重置改用self成员变量或nonlocal声明返回了最右侧节点递归顺序先右后左交换dfs递归左右子树的顺序遇到深层树直接崩溃Python递归深度超限改用BFS迭代版本空树或单节点树结果不对没有处理root为空或根节点深度没初始化好判断空树返回默认值根深度与max_depth初始值对齐5. 一道513串起一整片二叉树题5.1 一题三变右视图、最大深度、层均值LeetCode 513最让我喜欢的一点是它能牵出一整串经典题目几乎可以当作一个知识点总结专题来刷。如果你把BFS里记录每层第一个节点改成每层最后一个节点会得到 LeetCode 199 二叉树的右视图。如果你把DFS里depth max_depth的更新逻辑单独抽出来只记录最大深度不做节点值记录会得到 LeetCode 104 二叉树的最大深度。如果把层序遍历里的每个节点值累加并除以每层节点数量会得到 LeetCode 637 二叉树的层平均值。也就是说513这道题其实是这组题目里最综合的一题它同时涉及层序、深度、每层首节点三个维度。你在吃透513之后再去刷199和104会感觉那些题目几乎是删掉某些代码就能得到的。5.2 变体一要求返回左下角的完整路径面试官可能在513基础上追加一问不光返回左下角的值还要返回从根到左下角节点的路径。这要求DFS在记录答案时顺便记录当前递归路径。class Solution: def findBottomLeftValue(self, root): self.max_depth -1 self.answer_path [] def dfs(node, depth, path): if not node: return path.append(node.val) if depth self.max_depth: self.max_depth depth self.answer_path path[:] # 拷贝当前路径 dfs(node.left, depth 1, path) dfs(node.right, depth 1, path) path.pop() dfs(root, 0, []) return self.answer_path注意path[:]这一步不能省。直接赋值self.answer_path path的话后面递归回溯时path.pop()会把已经记录的路径改坏最终答案变成空列表。我一开始就是没拷贝输出结果一直对不上加上[:]就好了。这个坑非常典型值得单独记一笔。5.3 变体二从二叉树BFS到矩阵BFSBFS不只是二叉树能用。LeetCode 994腐烂的橘子、LeetCode 1162地图分析都是在二维矩阵上做BFS。它们的共同点是每次扩散一层分钟/步数经过几次扩散后统计结果。513里的层在矩阵题中对应轮或分钟队列的核心思想完全一致。如果513你已经写得非常顺我建议立刻去刷一遍994腐烂的橘子。你会发现它本质上就是从多个起点同时开始做BFS计算扩展到全图需要多少层。这种从一个点到多个点、从树到图的跳跃是刷题进阶时特别重要的思维训练。最后再分享一个我自己刷题时的习惯像513这种题我一般先写BFS版本保底保证至少能过再写DFS版本验证自己对递归深度的理解。面试时如果时间够两种解法都讲一遍重点对比它们的空间复杂度差异这比单纯背答案要加分得多。但如果你时间紧优先掌握BFS反向入队法因为它代码最短最不容易出错也最容易在高压环境下临场写对。刷题不在多而在把一道题真正吃透。513就是那种值得反复回味的题目——从它出发二叉树的核心考点能串起一大片。
LeetCode 513找树左下角的值：BFS层序遍历与DFS递归深度全解
LeetCode 513这道题我的建议是每一位刷二叉树专题的人都要把它做透。题目名字叫《找树左下角的值》给定一棵二叉树返回最后一层最左边的节点值。它难度不高却在一道题里同时踩中了层序遍历、递归深度、边界处理三个考点非常适合当作二叉树知识点的总结题来对待。这篇内容不会只丢一个能过的答案我会把两种主流解法、背后的思考路径、刷题时容易踩的坑以及从这道题延伸出去的一串经典题目一次讲透。如果你正准备面试或者在系统刷LeetCode热题100和二叉树专项这篇正好对路。新手可以直接照抄代码加注释跑通有经验的也能在反向入队法递归深度控制这些细节里找到一点新东西。1. 题目到底在问什么先拆解左下角三个字1.1 一句话说清题目我给你翻译成人话一棵二叉树从上到下分了很多层你要找到最深的那一层然后在那一层里找出最靠左的节点返回它的值。题目原描述里经常出现一个词——bottom left。LeetCode 513的原题是英文的中文社区翻译过来有叫找树左下角的值也有叫最底层最左边的值都指向同一个定义。注意这个定义有两个限定条件第一必须是最后一层第二必须是这一层里最左边的节点。两个条件缺一不可。有一个隐藏性质值得多说一句二叉树的最后一层节点其实全部都是叶子节点。因为只要某个节点还有孩子那孩子所在的层一定比它更深它就不可能是最后一层的节点。所以这道题本质上就是找到最深层的那一组叶子取最左边的一个。这个性质对理解DFS解法里的叶子判断会很有用。1.2 第一层坑左下角不等于一路向左很多人看到左下角三个字第一反应是从根节点一路往左走到底不就行了。这个直觉在大部分入门二叉树文章里是被反复灌输的但放到这道题上它是错的。我举个例子1 / \ 2 3 \ 4如果按一路往左走你会得到节点2但这棵树的最后一层是深度2的那一层这一层只有一个节点4所以左下角的值应该是4不是2。问题就出在最左必须满足最深这个前提。再看一个反例1 / \ 2 3 / \ 4 5这棵树的最后一层是深度2节点4和5都在这一层左下角是4。一路往左走恰好也能到4属于碰巧。但前面那个例子已经说明没有深度信息加持的向左路径根本不能保证到达最后一层。这也是为什么这道题被很多老师拿来当知识点总结题的原因——它逼着你把层次深度最左这三个概念分开想清楚然后再缝合到一起。2. BFS层序遍历最稳的一版解法2.1 层序为什么是天然答案BFS层序遍历的逻辑是从上到下一层一层访问同一层内部按照从左到右的顺序处理。既然题目要的就是最后一层第一个节点层序遍历几乎就是照着答案写的——你只需要在遍历过程中记录每一层的第一个节点最后一层记录到的那个就是结果。如果不用显式地记录每层第一个还有一种更巧妙的做法既然我们最终要的是最后访问的那个节点那只要调整同层节点的入队顺序让每一层都从右往左遍历那么整棵树遍历过程中最后被访问到的节点天然就是最后一层最左边的节点。这就是很多题解里说的反向入队法。这两种思路一种直白一种精巧我都会给出完整实现。2.2 写法一记录每层第一个出队节点Python最常见的层序遍历版本用队列保存当前层的节点每层处理完后进入下一层。关键点在于每层循环里第一个从队列里弹出的节点就是这一层最左边的节点。from collections import deque class Solution: def findBottomLeftValue(self, root): if not root: return -1 queue deque([root]) leftmost root.val while queue: size len(queue) for i in range(size): node queue.popleft() if i 0: leftmost node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) return leftmost这里for i in range(size)里的size必须在进入循环前用len(queue)保存下来不能写成for i in range(len(queue))原因后面第4节会专门讲。leftmost变量是不断被覆盖的每处理完一层它就更新成那一层最左边的值所以循环结束时它自然就是最后一层最左边的值。这个版本比较符合直觉面试时先在白板上写这个基本不会出错。2.3 写法二反向入队法Python Java第二种写法非常飘逸也是很多官方题解喜欢用的版本。核心就一句话每次出队一个节点先把右孩子入队再把左孩子入队整个遍历顺序就会变成同一层从右往左层与层从上往下最终最后一个出队的节点就是左下角。from collections import deque class Solution: def findBottomLeftValue(self, root): queue deque([root]) node root while queue: node queue.popleft() if node.right: queue.append(node.right) if node.left: queue.append(node.left) return node.val为什么出队顺序会变成从右往左我画个最简单的例子1 / \ 2 3 / \ / \ 4 5 6 7队列初始是[1]。弹出1把右孩子3放进去再把左孩子2放进去队列变成[3, 2]。接下来弹出3放入它的右孩子7和左孩子6队列变成[2, 7, 6]。再弹出2放入5和4队列变成[7, 6, 5, 4]。你看第二层节点从右往左弹出第三层也是从右往左弹出最后一层最左边的是4它在最后才被弹出。这个版本少了一个leftmost变量逻辑更紧凑。Java版本同样简洁class Solution { public int findBottomLeftValue(TreeNode root) { QueueTreeNode queue new LinkedList(); queue.offer(root); TreeNode node root; while (!queue.isEmpty()) { node queue.poll(); if (node.right ! null) queue.offer(node.right); if (node.left ! null) queue.offer(node.left); } return node.val; } }我实测下来这个解法在LeetCode 513上时间和内存表现都很好代码也少。但有个前提你要能熟练解释为什么最后一个出队的节点就是左下角如果面试官追问而你自己都没画过例子容易被带崩。2.4 BFS的时间与空间复杂度BFS的时间复杂度是 O(n)n是二叉树节点个数因为每个节点都恰好入队出队一次。空间复杂度取决于队列在任意时刻最多能装多少节点也就是二叉树的最大宽度。最坏情况下比如一棵满二叉树最后一层节点数约 n/2所以空间复杂度最坏是 O(n)。这个复杂度水准对 LeetCode 513 的数据规模节点数最多一万多来说完全没压力。但如果你要写递归版复杂度的解释方式就完全不同了见下一节。3. DFS递归解法手动补上深度这个维度3.1 核心思路首次到达该深度的节点就是最左DFS深度优先搜索天然不带层的概念它关心的是深度。好在我们可以用递归函数的参数把深度逐层传下去然后在遍历过程中记录一个见过的最大深度。这套逻辑的关键在于一个判断每当某个节点所在的深度大于当前记录的最大深度就更新答案。因为DFS先走左子树再走右子树所以每个深度第一次被解锁的时候访问到的那个节点一定是这一层最左边的节点。之后同层的其他节点再访问到时深度不再大于已记录的最大深度也就不会覆盖答案。用生活化的类比你拿着一个本子往地下停车场一层层走每到一个新楼层第一次见到的深度就在本子上写下这一层第一个看到的车位号。之后在这一层看到其他车位一律不记。等你把整栋楼走完本子上最后一条记录就是最深一层第一个看见的车位。3.2 Python实现与逐行注释class Solution: def findBottomLeftValue(self, root): self.max_depth -1 self.answer 0 def dfs(node, depth): if not node: return # 核心判断首次到达当前深度 if depth self.max_depth: self.max_depth depth self.answer node.val # 先左后右保证同一深度优先访问最左节点 dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return self.answer这里self.max_depth初始化为 -1是因为根节点的深度是0而 -1 小于0所以根节点一定会在第一轮被记录为答案。如果你习惯让根节点深度是1那max_depth就初始化为0逻辑一模一样。self.answer会被不断覆盖只有当depth self.max_depth时才更新。整个DFS走完后answer保存的就是最深一层最左边的节点值。3.3 为什么必须先左后右如果把代码改成先递归右子树、再递归左子树会得到什么答案会变成右下角。因为每个深度第一次被访问到时是从右子树路径到达的记录的自然是这一层最右边的节点。这个顺序极其容易被忽略。我自己第一次写这个解法时凭直觉先写了dfs(node.left)再dfs(node.right)刚好对了。但后来想改成从右往左版本的题目时发现只要把两行顺序换一下就行。这说明先左后右不是代码习惯而是跟答案绑定的必要条件。如果你想在面试里展示自己对这个细节的理解可以主动跟面试官说一句这里递归顺序是关键先访问左子树保证了更新条件触发时记录的是最左节点。3.4 递归深度的边界问题DFS递归在刷题时有个隐患递归深度。Python默认递归深度上限是1000层LeetCode上二叉树的深度最坏可以到一万甚至更多。如果测试用例给了一棵链状树每个节点只有左孩子DFS递归到第1001层就会抛出RecursionError。我在实际做这道题时没有踩到递归深度的坑因为513的测试数据对DFS是友好的。但如果是自己扩展练习或者把代码搬到一个节点特别多的场景BFS迭代版本就不会有这个问题。这是面试时选择BFS的一个正当理由你不仅能给出正确的答案还能解释为什么在极端输入下BFS比DFS更稳。如果面试官坚持要你写DFS也可以给出一个补充方案显式用栈做迭代版DFS。但坦白说迭代DFS模拟递归的先序、中序、后序过程比BFS麻烦不如直接用BFS。4. 刷题现场常见的四个错误4.1 队列size提前保存的失误第一个高频错误发生在BFS写法里。新手容易写出下面这种代码while queue: for i in range(len(queue)): node queue.popleft() ...表面上看range(len(queue))在每次循环开始时计算一次长度好像没什么问题。但在Python里range的参数只在生成range对象时求值一次之后循环次数就固定了。所以这种写法其实是能用的它等于在进入for循环前把当时的len(queue)快照了下来。真正出错的是Java或C里常见的写法while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i queue.size(); i) { // 每次循环都重新取值 TreeNode node queue.poll(); ... } }这里i queue.size()会在每次循环时重新计算size而poll操作又让队列变小导致循环次数不足一层没处理完就提前进入下一层。我见过不少人在IDE里单步调试才找到这个问题。所以代码规范要统一进入循环前先把size保存到一个局部变量里循环条件用这个局部变量判断。不管什么语言这个习惯都不亏。4.2 深度变量更新时机不对DFS版本的坑主要在成员变量的更新时机。如果你把max_depth和answer作为局部变量放进递归函数就会遇到每次递归栈都是新变量的问题。比如有的人会写def dfs(node, depth): max_depth -1 answer 0 ...这样每次递归进来都会把max_depth重新初始化为-1等于什么也没记录最终返回一个错误答案。正确的做法是要么把max_depth和answer定义成类的成员变量用self.前缀要么在嵌套函数里用nonlocal声明def findBottomLeftValue(self, root): max_depth -1 answer 0 def dfs(node, depth): nonlocal max_depth, answer ...nonlocal在LeetCode的编辑器里是支持的但很多面试场景下考官更习惯看到self.max_depth这种成员变量的写法不容易产生歧义。4.3 把左下角当成了最左叶子前面第1节提过最后一层的节点全部都是叶子。但这不意味着你可以直接写找到最左的叶子。举个反例1 / 2 / 3这棵树只有一条左链最后一层的节点是3它确实是最左叶子。如果题目改成返回整棵树最左边的叶子节点不论深度答案也是3碰巧一致。但下面这棵树就不一样1 / \ 2 3 / 4最后一层是节点4左下角是4。如果按最左叶子找从根节点开始2和4是叶子最左叶子是2那就错了。所以判断左之前必须先满足深这个前提。这也是DFS版本里我把更新条件设计为depth max_depth而不是如果是叶子就更新的原因。你可以在心里记一句话这道题不是找到最左的叶子而是找到最深层的首节点。4.4 递归栈溢出与元素取值错误递归栈溢出前面已经提过。还有一个不太容易被发现的取值错误如果二叉树节点值本身可以是任意整数那不要把answer初始化为一个特定的魔法值比如-1或0因为如果根节点的值恰好等于初始值会干扰判断。比如有人写self.answer -1而整棵树的根节点值正好是-1并且最后一层左下角也是-1那答案碰巧对。可如果左下角是0但代码对DFS的更新顺序理解错了导致缓存没更新就可能返回一个听起来很合理的错误值。正确思路是answer初始值无所谓反正只要正确执行DFS它一定会在第一轮被覆盖。真正决定答案的是max_depth的比较逻辑不是answer的初始值。4.5 常见问题速查表错误现象可能原因修复方案返回结果少了一层Java遍历时循环条件没保存size先用局部变量保存queue.size()再循环DFS返回根节点的值max_depth定义在递归函数内部被反复重置改用self成员变量或nonlocal声明返回了最右侧节点递归顺序先右后左交换dfs递归左右子树的顺序遇到深层树直接崩溃Python递归深度超限改用BFS迭代版本空树或单节点树结果不对没有处理root为空或根节点深度没初始化好判断空树返回默认值根深度与max_depth初始值对齐5. 一道513串起一整片二叉树题5.1 一题三变右视图、最大深度、层均值LeetCode 513最让我喜欢的一点是它能牵出一整串经典题目几乎可以当作一个知识点总结专题来刷。如果你把BFS里记录每层第一个节点改成每层最后一个节点会得到 LeetCode 199 二叉树的右视图。如果你把DFS里depth max_depth的更新逻辑单独抽出来只记录最大深度不做节点值记录会得到 LeetCode 104 二叉树的最大深度。如果把层序遍历里的每个节点值累加并除以每层节点数量会得到 LeetCode 637 二叉树的层平均值。也就是说513这道题其实是这组题目里最综合的一题它同时涉及层序、深度、每层首节点三个维度。你在吃透513之后再去刷199和104会感觉那些题目几乎是删掉某些代码就能得到的。5.2 变体一要求返回左下角的完整路径面试官可能在513基础上追加一问不光返回左下角的值还要返回从根到左下角节点的路径。这要求DFS在记录答案时顺便记录当前递归路径。class Solution: def findBottomLeftValue(self, root): self.max_depth -1 self.answer_path [] def dfs(node, depth, path): if not node: return path.append(node.val) if depth self.max_depth: self.max_depth depth self.answer_path path[:] # 拷贝当前路径 dfs(node.left, depth 1, path) dfs(node.right, depth 1, path) path.pop() dfs(root, 0, []) return self.answer_path注意path[:]这一步不能省。直接赋值self.answer_path path的话后面递归回溯时path.pop()会把已经记录的路径改坏最终答案变成空列表。我一开始就是没拷贝输出结果一直对不上加上[:]就好了。这个坑非常典型值得单独记一笔。5.3 变体二从二叉树BFS到矩阵BFSBFS不只是二叉树能用。LeetCode 994腐烂的橘子、LeetCode 1162地图分析都是在二维矩阵上做BFS。它们的共同点是每次扩散一层分钟/步数经过几次扩散后统计结果。513里的层在矩阵题中对应轮或分钟队列的核心思想完全一致。如果513你已经写得非常顺我建议立刻去刷一遍994腐烂的橘子。你会发现它本质上就是从多个起点同时开始做BFS计算扩展到全图需要多少层。这种从一个点到多个点、从树到图的跳跃是刷题进阶时特别重要的思维训练。最后再分享一个我自己刷题时的习惯像513这种题我一般先写BFS版本保底保证至少能过再写DFS版本验证自己对递归深度的理解。面试时如果时间够两种解法都讲一遍重点对比它们的空间复杂度差异这比单纯背答案要加分得多。但如果你时间紧优先掌握BFS反向入队法因为它代码最短最不容易出错也最容易在高压环境下临场写对。刷题不在多而在把一道题真正吃透。513就是那种值得反复回味的题目——从它出发二叉树的核心考点能串起一大片。
