刷题刷到LeetCode 513的时候，很多人第一眼会觉得这题很简单，但真正动手写的时候，才发现“左下角”三个字里面有坑——不是左子树的最左节点，不是整棵树的最左叶子，而是最后一层的最左边那个节点。LeetCode知识点总结 -513这个题目背后，其实串起了二叉树遍历、层序与深度优先的取舍、递归边界条件、迭代写法等多个核心知识点。这篇文章就围绕这一题，把题目拆开，把解法讲透，把常踩的坑也一并列出来，适合正在刷树的题、准备面试、或者想巩固二叉树遍历基础的同学。
1. 题目拆解：先看懂513在考什么
1.1 题目到底在问什么：不是找最左子节点，而是找最后一层的最左节点
LeetCode 513的原题是：给定一棵二叉树，返回这棵树底部最左节点的值。注意表述，是“底部”且“最左”。这里有两层限制：第一，必须是最下面一层，也就是深度最大的那一层；第二，在这一层里面，要找最左边的那个节点。
很多人会理解成“一直往左走，走到叶子节点”，这个理解是错的。举个例子：
1 / \ 2 3 / / \ 4 5 6 / 7如果按“一直往左”的思路走，路径是1->2->4，结果返回4。但正确答案是7，因为最后一层是深度为4的节点7、5、6那一层，最左边的是7。所以这道题考的不是简单的左倾路径，而是“深度优先和广度优先两种遍历方式的本质理解”。
我来画一下这棵树的结构帮助理解：
- 第1层：1
- 第2层：2, 3
- 第3层：4, 5, 6
- 第4层：7
最后一层最左是7，这就是答案。
1.2 这题背后的知识点清单
513这个题虽然标号靠后，但它在面试中出现的频率不低，原因是它一次性能考察多个知识点：
- 二叉树的两种遍历方式：深度优先搜索（DFS）和广度优先搜索（BFS）。
- BFS如何按层处理，尤其是每层从哪个方向入队。
- DFS递归时如何携带“当前深度”信息，以及如何判断“当前节点是否是某一层的第一个节点”。
- 递归和迭代的相互转换。
- 边界条件的处理：空树、只有根节点、只有左子树或右子树。
- 时间和空间复杂度的估算。
把这几个点搞明白，往后做类似的“找树最底层某个位置”的题目，比如找最右下角的值、找最左叶子节点，都能套用同一套思路。
2. 二叉树基础：先把数据结构内功补上
2.1 二叉树的定义与存储方式
二叉树的核心结构是节点，每个节点最多有两个孩子，分别叫左孩子和右孩子。在LeetCode里，二叉树节点的定义通常是这样的：
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right很多同学对于“节点”这个概念一开始不适应，总把它想得太抽象。其实你可以把二叉树想象成一份公司组织架构：每个节点是一个员工，每个员工最多带两个直属下属，一个管左侧业务，一个管右侧业务。那么整棵树就是从这个组织架构的顶层一路展开下去。
在算法题里，我们操作的就是这些节点以及它们之间的指针关系。树的存储不需要像数组那样连续，只要每个节点能通过left和right指针找到它的孩子，整棵树的结构就完整了。
2.2 树的遍历分类：DFS与BFS
树的遍历大体分成两类：
深度优先搜索（DFS）：沿着一条路走到黑，再回头走下一条路。实现上常用递归或显式栈。常见的先序、中序、后序都属于DFS。
广度优先搜索（BFS）：一层一层往下扫，同一层的节点按从左到右（或从右到左）的顺序逐个访问。实现上常用队列。
理解这两者的区别，有一个很直观的生活类比：DFS像考古学家走迷宫，先一直往里探，探到死路再退回来换一条通道；BFS像在水面丢一颗石子，波纹一圈一圈往外扩，先覆盖离起点最近的一圈，再覆盖下一圈。
回到513题，我们要找的是“最后一层”的最左节点。既然强调层，BFS天然就是一层一层往下扫，扫到最后一层后，取那一层的左边界即可，思路非常直接。DFS也能做，只是需要额外记录深度信息和“该层是否已找到过节点”的状态。
2.3 为什么这题适合用层序遍历
如果只看“找最大深度那层的最左节点”，其实DFS和BFS都可行。但从面试沟通和代码可读性来看，BFS更直观，因为BFS本身就把“层”的概念天然带出来了。
用BFS时，你不需要管当前深度是几，只需要知道：当队列为空时，最后一个被访问的节点就是最后一层的最右节点；或者反过来说，如果每一层都从右往左扫描，那么队列里最后一个被弹出的节点就是最后一层的最左节点。
这个“从右往左扫”的技巧非常实用，代码量也少。很多解法直接采用这个思路：
- 根节点先入队。
- 循环过程中弹出节点，先把右孩子入队，再把左孩子入队。
- 这样整个队列访问顺序是：每一层从右到左。
- 当队列遍历完，最后一次弹出的节点，就是整棵树最后一层的最左节点。
等于说，这个问题被转化成了“BFS最后一个访问到的节点是谁”。
3. 解法一：BFS层序遍历（推荐解法）
3.1 思路拆解：从右往左层序的巧妙之处
BFS的标准做法是维护一个队列。起初队列里只有根节点，然后循环：从队首取出一个节点，把它的左孩子、右孩子依次入队。这个顺序保证同一层从左到右被访问。
如果我们反过来，先把右孩子入队，再把左孩子入队，那么同一层就是从右到左被访问。这样当整棵树被遍历完时，最后一个被访问的节点，一定是最后一层最左边的节点。为什么？因为层级越深的节点越晚被访问，而同一层内，从左到右看，左孩子在右孩子之后入队，所以左孩子比右孩子更晚被访问，最后访问到的就是该层最左的节点。结合“层深”和“层内顺序”两个维度，最终答案就是最后一个节点。
这个方法不需要记录深度，不需要判断当前节点是第几个，甚至不需要额外变量来保存答案，只需要在每次弹出节点时更新一次返回值即可。
3.2 代码实现与逐行注释
Python实现如下：
from collections import deque class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: # 如果树为空，题目说不存在这种情况，但为了严谨可以返回一个默认值 if not root: return -1 queue = deque([root]) result = root.val while queue: node = queue.popleft() # 因为是从右往左入队，所以最后弹出的就是最左下角节点 result = node.val # 先入右孩子，再入左孩子 if node.right: queue.append(node.right) if node.left: queue.append(node.left) return result这段代码的逻辑很简洁。注意几个细节：
- 使用
deque而不是list，因为list的pop(0)是O(n)操作，deque的popleft()是O(1)。 - 入队顺序是右孩子先、左孩子后，这是整个解法的灵魂。
- 结果不断被覆盖，最后一次覆盖的值就是答案。
运行示例：
输入： 1 / \ 2 3 / / \ 4 5 6 / 7 队列变化： 初始 [1] 弹出1，入队右3，入队左2 -> [3, 2]（注意这里队首是3） 弹出3，入队右6，入队左5 -> [2, 6, 5] 弹出2，入队右4（2没有右孩子，所以跳过），入队左4 -> [6, 5, 4] 弹出6，入队右、左都无，跳过 弹出5，入队右（无），入队左7 -> [4, 7] 弹出4，无孩子 弹出7，无孩子，result=7 返回7注意上面队列我用箭头表示方向，实际上popleft取的是队首。我描述的“队列 [3, 2]”中，下一个弹出的是3，这符合从右往左的顺序。
3.3 复杂度分析：为什么这个写法够优
时间复杂度上，每个节点只会被访问一次，因此总时间O(n)，n是节点总数。空间复杂度上，队列中最多同时存储一层的节点数。对于满二叉树，最后一层节点数约为n/2，所以空间复杂度是O(n)最坏情况；如果树比较平衡且层数高，也可以理解为O(w)，w是树的最大宽度。
面试里问复杂度时，建议准确说：
- 时间：O(n)
- 空间：最坏情况下O(n)，因为队列需要存储一整层的节点；在极端情况下（比如链状树），队列里最多只有1个节点，空间为O(1)，但整体按最坏算。
这个复杂度已经是最优的，因为任何解法都要看遍所有节点才知道哪一层最深、最左节点是谁，所以不可能低于O(n)。
4. 解法二：DFS递归与迭代的另类思路
4.1 递归写法：用深度换答案
BFS虽然直观，但有时面试官会追问“不用队列能不能做”，或者考察你对DFS的理解。这时候可以给出DFS版本。
DFS的思路是：从根节点出发，按“先左后右”的顺序遍历整棵树。我们记录两个全局信息：
- 当前遇到的最大深度。
- 在这个最大深度下，第一个遇到的节点的值。
因为同一深度下，先遍历到的一定是最左节点，所以只要某个节点深度大于当前最大深度，就更新答案。等于说，把“最底层最左”分解成“深度最大”和“同层先左”两个条件。
递归代码：
class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: self.max_depth = -1 self.result = root.val def dfs(node, depth): if not node: return # 因为是先左后右遍历，所以同一深度下第一次到达的节点就是最左节点 if depth > self.max_depth: self.max_depth = depth self.result = node.val # 先递归左子树，再递归右子树 dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root, 0) return self.result这里的关键是depth > self.max_depth这个判断。注意用的是严格大于，不是大于等于。如果当前深度和最大深度相等，说明这一层前面已经遇到过节点了，那么当前节点不可能是这一层最左的节点，所以我们不更新结果。这正是“先左后右”顺序带来的效果。
4.2 迭代栈模拟：不用递归也能DFS
如果面试官要求不能递归，可以用栈来模拟DFS。但要注意，栈是后进先出，所以入栈顺序要和递归顺序相反。递归是先处理左子树再处理右子树，那么用栈时，要先压右子树再压左子树，这样弹出时才会先处理左子树。
实现代码如下：
class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: max_depth = -1 result = root.val stack = [(root, 0)] while stack: node, depth = stack.pop() if node: if depth > max_depth: max_depth = depth result = node.val # 注意：先压右子树，再压左子树，出栈顺序才是先左后右 if node.right: stack.append((node.right, depth + 1)) if node.left: stack.append((node.left, depth + 1)) return result很多同学写迭代DFS时习惯顺手先压左再压右，结果发现遍历顺序变了。记住一个原则：递归先做哪边，迭代就先压哪边对应的相反方向。因为栈是反过来的。
4.3 两种DFS写法的取舍
递归写法简洁，代码量少，逻辑清晰，缺点是如果树特别深，可能造成递归栈溢出。在LeetCode上，树的深度一般不会大到溢出，但在生产环境或者面试讨论时，可以提一句“迭代栈写法避免了递归深度限制”。
迭代写法稍微繁琐，需要自己维护一个node和depth的二元组，但可控性强。日常刷题，我更推荐先掌握递归版本，因为它和直觉一致，方便快速写出正确代码；同时也要理解迭代版本，因为面试中经常考察“递归改迭代”的基本功。
如果和BFS版本对比，DFS版本的优势是空间复杂度在最坏情况下是O(h)，h是树高，对于倾斜的树h=n，对于平衡树h=log n，通常比BFS的O(w)小一些。不过这不是决定性的，面试时选自己最有把握、讲得最清楚的写法就好。
5. 常见错误与排查技巧
5.1 空树边界处理
LeetCode 513的原始约束是树节点数量至少为1，所以空树不会出现在测试用例里。但如果你自己写工具函数，或者面试官加了一道变体，空树可能导致root.val直接报错。
稳妥做法是在函数开头加判断：
if not root: return None有人会问返回什么好？这取决于场景。面试时可以说“根据题目约定，空树不会出现；如果扩展场景，可以返回None或者抛异常”。这样的回答能体现你对边界条件的敏感度。
5.2 左右子树顺序陷阱
这是513题最容易被忽略的坑。如果用BFS从右往左入队，顺序一定不能写反，要先right后left。如果写反了，最后弹出的节点就成了“最右下角”了，整道题就变成了LeetCode 513的反向版本。
我见过不少同学背模板背得熟，一上来就写if node.left: queue.append(node.left)，结果交上去发现答案错误，排查半天才看出是入队顺序的问题。调试这种问题最快的办法是，找一个只有两层的小树，比如[1,2,3]，手动模拟一遍队列的顺序变化，立刻能发现问题。
5.3 递归参数传递的坑
在DFS递归写法中，depth参数是随着递归调用往下传的，每个子树都有自己的深度。有人容易把depth写成全局变量，然后在递归函数里直接修改，这样可能造成混乱。
比如错误写法：
self.depth += 1 dfs(node.left) self.depth -= 1这种写法不是不行，但要非常小心回溯时递减。复杂树结构下一旦漏掉减回去，深度就会越加越大，答案就会错。与其这样，不如直接用depth + 1作为参数传给下一层，干净并且不容易出错。
5.4 实战排错记录
我自己刷这道题时，第一次用的是DFS递归，结果在更新深度时写成了if depth >= self.max_depth，导致同一层左边的节点被右边节点覆盖，答案从7变成了6。当时对着示例看了很久才意识到，问题不是遍历顺序，而是更新条件应该严格大于。
后来我把判断改成>，问题就解决了。这个细节很微小，但很关键。>=适合“找最右节点”的场景，>适合“找最左节点”的场景。理解这个区别后，遇到类似的“下一层第一个节点”题目都能举一反三。
还有一个关于BFS的坑：有人会想用两个队列模拟分层，结果写多了判断，反而出错。记住我们用的“从右往左整体层序”技巧，不需要显式分层，只需要最后弹出的节点就是答案。这个技巧在“找最右下角节点”时，把入队顺序反过来即可。
6. 面试中怎么答这道题
6.1 从暴力到最优的思考路径
如果面试官让你现场写这题，不要上来就背代码，而是展示思考过程。可以这样讲：
“最直接的想法是遍历整棵树，维护两个信息：当前最大深度，以及这个深度下最左节点的值。由于要先保证深度最大，再保证同层最左，所以在DFS中先左后右遍历，深度严格大于当前最大深度时更新答案。另一种思路是BFS，如果需要更直观的层次关系，可以从右往左层序遍历，最后一个节点就是答案。”
这段话能同时展示你对DFS和BFS的理解，面试官通常会认可。如果面试官追问时间空间复杂度，也能顺势讲清楚O(n)和O(w)或O(h)的区别。
6.2 扩展变体与进阶思考
513题有很多变体，面试时可能会被问到以下问题：
- 找最底层最右节点的值。怎么做？把BFS入队顺序改成先左后右，最后弹出的就是最底层最右节点；DFS则把左右遍历顺序反过来，更新条件也配合调整。
- 找最底层所有节点的值。怎么做？需要层序遍历并记录每层节点，或者DFS时把每层的节点都收集到对应层级的列表里，最后取最后一层。
- 如果树不是二叉树，而是多叉树呢？方法类似，把“左孩子”“右孩子”改成遍历所有子节点，但要注意“最左”的定义：一般指子节点列表中的第一个。
- 如果要求返回节点的路径而不是值呢？需要在遍历时记录路径，DFS更适合，因为可以维护路径栈。
这些扩展题能帮助你更深入地理解二叉树遍历的本质，而不是单纯背题。
6.3 个人刷题心得
我刷了这么多树的题目，最大的体会是：树的题其实就两类，一类考遍历，一类考递归结构。513属于前者，但它又和递归紧密相关。很多同学喜欢一道题一道题硬刷，刷完就忘，这样效率太低。我自己的方法是，每次遇到一个题型，就把它和已经做过的题建立联系。
比如513题，你可以在笔记里这样记：
- 和“找树左下角的值”相关的BFS套路：从右往左层序，最后弹出即答案。
- 和“找最大深度”相关的DFS套路：维护最大深度变量，在递归时更新。
- 和“层序遍历”相关的代码模板：队列+循环。
这样记下来，以后做题遇到类似问题，就能快速匹配到对应模板，而不是重新推导一遍。
另外，我建议新手先用手画一棵三层以上的树，把BFS队列手动模拟一遍。不要只在脑子里想，拿纸画一画，比看十遍题解都管用。等模拟熟练之后，再写代码，会顺畅很多。
这道题本身难度不高，但它是一个很好的分水岭：能清晰讲出DFS和BFS各自怎么解、为什么更新条件是严格大于、入队顺序为什么影响答案的人，说明对二叉树遍历的基本功是扎实的。刷题不在于数量，而在于每道题你真正消化了多少。把513题吃透，往后遇到树相关的问题，你会顺手很多。
