1. 从一道题看二叉树遍历的核心考点1.1 LeetCode 513到底在考什么LeetCode 513这题题目全称叫找树左下角的值对应的英文是Find Bottom Left Tree Value。很多第一次刷到这道题的人第一眼看到左下角三个字会下意识以为要一路向左走到最底层。等真正动手写代码才发现题目要求的是先找到二叉树最深的那一层再取这一层最左侧节点的值。先深后左优先级一反过来思路就完全不一样了。这道题给定的是一个非空二叉树要求返回最底层最左边节点的值。官方难度定的是中等但坦白讲这道题在中等里算是非常友好的那一档。它不涉及什么复杂的算法技巧本质就是二叉树遍历的两种基本功——广度优先搜索BFS和深度优先搜索DFS。之所以被定为中等是因为它把层数和左右顺序这两个维度叠加在一起考察你对遍历过程的理解是否够细。我刷题这些年越来越觉得513这类题是很好的试金石。它不像动态规划那样需要大量练习才能建立感觉也不像并查集那样需要预先了解数据结构它就是纯粹的二叉树遍历但恰恰是这种基础题最能看出一个人对BFS和DFS的理解是背模板还是真懂了。你要是能把这道题从里到外讲明白二叉树遍历这块的基础基本就夯实了。1.2 为什么左下角是个容易踩坑的概念先说一个我见过的经典翻车现场。有同学一上来就写递归每次都先往左子树走一路走到叶子节点然后把结果返回。遇到下面这棵树时会直接出错1 / \ 2 3 / / \ 4 5 6 \ 7最底层是深度4那一层节点只有7一个所以左下角的值是7。但如果只是一路向左走到的是4显然不对。因为题目要的是最深的层而不是最靠左的路径。另一个容易混淆的点是左下角和最底层最左边的区别。有的树最底层只有一个节点那它既是唯一的节点也是最左边的节点有的树最底层有多个节点这时候要的是这一层第一个最左边那个。比如下面这棵1 / \ 2 3 / \ \ 4 5 6 \ 7最底层是深度4只有7一个节点所以答案是7。再比如1 / \ 2 3 / \ / \ 4 5 6 7最底层是深度3这一层有4、5、6、7四个节点左下角是4。这些例子说明一个核心原则先确定最深这个约束再考虑最左这个约束两个条件缺一不可顺序也不能颠倒。理解了这一点这道题的解题方向就清晰了——本质上就是一次完整遍历在遍历过程中同时维护当前深度和该深度下的最左节点这两个信息。2. 解法一BFS层序遍历的两种思路2.1 从右到左的反向思维BFS层序遍历大家都很熟用队列先入根节点然后一层一层往外扩展。但513这题如果用BFS有一个非常巧妙的切入点——让每一层的节点按照从右到左的顺序入队这样最后一个出队的节点一定是最底层最左边的节点。这个思路妙在哪里我们来推演一遍。标准层序遍历是从左往右假设当前层有[a, b, c]三个节点按顺序处理后它们的孩子节点会依次进入队列。如果我们改成从右往左处理也就是先处理c、再处理b、最后处理a那么下一层的节点入队顺序就变成了右边的孩子先入左边的孩子后入。队列是先进先出的所以越靠左的节点越晚出队。当我们把整棵树完整遍历完队列清空的那一刻最后一个出队的节点是什么是最底层最后入队的那一批节点中最后出队的一个。因为每一层都是从右往左处理所以最底层最后出队的那个节点恰好就是这一层最左边的节点。整个推导环环相扣一句话总结就是反向层序遍历最后出队的节点就是答案。from collections import deque def findBottomLeftValue(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核心就三行逻辑出队、右孩子入队、左孩子入队。循环结束后node变量指向的就是最后一个出队的节点。我第一次看到这个写法的时候愣了一下因为它短得不像一道中等题。但仔细想想这正是BFS特性的精准利用——你不需要手动记录层数不需要在每一层结束时做判断甚至不需要额外变量保存答案队列本身帮你完成了所有工作。2.2 从左到右记录每层首个节点如果你觉得从右到左的写法有点炫技那从左到右的传统层序遍历其实更符合直觉。思路很简单逐层遍历记录每一层第一个出队的节点遍历结束后最后一次记录的节点就是最底层的最左节点。from collections import deque def findBottomLeftValue(root): 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这里有个关键操作在每一层开始之前先用size len(queue)记录当前层的节点数然后只循环size次。为什么要这样因为队列在遍历过程中会不断加入下一层的节点如果不固定循环次数你就分不清哪些是当前层的节点、哪些是下一层的。size相当于给这一层画了一条分界线这是层序遍历的经典手法在二叉树右视图、锯齿形遍历等题目里都会用到。i 0判断的是当前层第一个出队的节点。因为我左孩子先入队左孩子比右孩子先出队所以第一个出队的天然就是最左节点。整个遍历结束后leftmost被每一层的第一个节点依次覆盖最终留下的一定是最后一层的第一个节点。这个写法思想上更直白代码也容易记适合面试时作为首选方案讲给面试官听。我个人的习惯是面试优先讲从左到右的笨办法讲清楚思路后再提一嘴从右到左的巧妙写法。这样既展示了基础功又体现了你对BFS理解的深度。2.3 BFS解法的复杂度分析两种BFS写法的时间复杂度和空间复杂度完全一致。时间复杂度是O(n)因为每个节点恰好入队一次、出队一次。空间复杂度是O(n)因为队列中最多同时存在某一层的全部节点满二叉树的最底层节点数大约是n/2所以数量级就是O(n)。这道题n的范围一般题目里会给出通常是[1, 10^4]级别完全不构成压力。但这个复杂度分析不是走过场面试官可能会追一句你的BFS空间复杂度能不能优化。从右到左的写法其实在空间上没有任何额外优化它还是存了所有节点和从左到右的写法空间复杂度相同。真正能优化空间的是后续要讲的DFS写法递归栈的深度是O(h)h是树高在极端情况下才退化成O(n)。还有一个细节值得注意从右到左的写法里queue.popleft()用的是双端队列的左侧弹出操作底层是链表实现的O(1)复杂度。你要是用Python的list模拟队列用pop(0)弹左侧元素那是O(n)的一旦数据量上来性能差距会非常明显。这也是为什么所有BFS代码都默认用from collections import deque这个习惯在刷题时要养成。3. 解法二DFS递归如何追踪深度3.1 深度优先的核心逻辑如果你对BFS的层序遍历已经炉火纯青那DFS解法的思路也一通百通。DFS的核心思想是带着当前深度去遍历每当发现一个节点比之前记录的最大深度更深就把这个节点的值记为答案因为是先遍历左子树再遍历右子树所以同一深度下第一次更新的节点一定是最左边的。这里面的关键在于更新时机。不是遇到新节点就更新而是只在depth maxDepth时才更新。这么做的好处是同一层的节点只有第一个被访问到的也就是最左边的会触发更新后面的节点深度和maxDepth相等不会覆盖之前的答案。比如在最底层有[4, 5, 6, 7]四个节点DFS先遍历到4此时深度是3大于之前记录的maxDepth2所以maxDepth更新为3答案更新为4。紧接着遍历到5深度也是3但不大于maxDepth3所以不更新。6和7同理。最终答案就是4完美命中最底层最左边。def findBottomLeftValue(root): max_depth -1 result root.val def dfs(node, depth): nonlocal max_depth, result if node is None: return if depth max_depth: max_depth depth result node.val dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return result这段代码里nonlocal是关键Python中嵌套函数要修改外层函数的变量必须用nonlocal声明否则会报错或者产生局部变量遮蔽。很多人在IDE里写这段代码时遇到UnboundLocalError十有八九是忘了这一行。3.2 递归代码的关键细节递归解法里有几个细节点睛之笔逐一说一下。第一max_depth的初始值设为-1。为什么不设为0因为根节点的深度是00 -1成立所以根节点一定会触发第一次更新把result初始化为根节点的值。如果你把max_depth设为0那当根节点深度为0时0 0不成立result就不会被初始化。当然你可以在外层直接把result设为root.val来绕开这个问题但这样代码就多了一行也少了那种所有节点都通过统一逻辑更新的优雅感。第二递归时depth 1而不是depth。函数式传参不修改当前变量的值每条递归路径都有自己独立的depth副本互不干扰。这是递归里非常基础但重要的概念——参数传递是值传递每个栈帧里的depth只代表当前路径的深度。第三先递归左子树再递归右子树。顺序能反吗如果先右后左那同一层第一个被访问到的节点就是最右节点答案就错了。所以左右顺序不能调换。这也是利用DFS天然顺序的一个典型体现。第四为什么这个解法能处理只有一个节点的树假设树只有一个根节点DFS进入后depth0 -1成立result被设为根节点值然后左右子树都是空直接返回。整个流程没有访问任何其他节点结果就是根节点值逻辑自洽。DFS在空间上比BFS有优势递归栈的深度等于树高h最坏情况下树退化成链表时是O(n)平均情况下是O(log n)。如果你在面试中被追问能不能用O(height)空间解决DFS就是你要给出的答案。3.3 迭代式DFS栈的写法如果不想写递归或者怕递归深度超过Python默认的1000层限制可以改成手动用栈模拟DFS。但这里有个小陷阱栈是后进先出的你要保证左子树先被处理就必须让右子树先进栈这样左子树才会后进先出地先被弹出。def findBottomLeftValue(root): max_depth -1 result root.val stack [(root, 0)] while stack: node, depth stack.pop() if node is None: continue if depth max_depth: max_depth depth result node.val # 栈是LIFO右先入栈左后入栈弹出时左先出 if node.right: stack.append((node.right, depth 1)) if node.left: stack.append((node.left, depth 1)) return result有人可能会问这里和递归的顺序还能保持一致吗能。递归的本质就是系统栈我们手动用栈模拟的是同一套逻辑。right先入栈、left后入栈弹出的顺序就是left先出、right后出和递归版本先处理左子树完全一致。代码里我还特意做了一个小优化——node为空时直接用continue跳过省得在入栈时就做大量非空判断。迭代写法在刷题时不一定用得上但它体现了你对递归本质的理解面试官如果问递归会不会爆栈怎么解决你能立刻给出这个方案会比只说把递归改成迭代更有说服力。4. 常见误区与调试技巧4.1 概念混淆左下角不是左子树路径这道题错得最多的认知误区就是把左下角理解成从根节点一路往左走到最底。我见过有人用while root.left: root root.left这种代码来解还觉得自己思路很简洁。这种解法在恰好最左路径就是最深路径的树上碰巧能过换个形状就立刻失效。举一个极端的例子1 \ 2 \ 3 \ 4这棵树全是右子树一路往左走根本走不动。但它的最底层是深度3那一层只有节点4所以左下角是4。如果按一路向左的思路你甚至找不出任何左孩子结果就是初始值答案整个漏掉。这种反例在面试时很有用你可以现场画给面试官看既展示了边界思维也证明你真的理解了题意。另一个相关误区是混淆深度和高度的概念。有的教材里根节点深度是1有的定义是0。代码里把根节点的深度定义成多少直接影响了max_depth的初始值和更新逻辑。只要自己在代码里保持一致两种定义都能写对但面试答到复杂度或状态转移时口径一定要统一。我习惯用0作为根节点深度这样很多二叉树公式比如完美二叉树第k层节点数是2^k更顺。4.2 队列/栈操作中的细节坑BFS解法里最容易犯的一个错误是入队顺序写反。你如果在从右到左的写法里把左孩子先入队、右孩子后入队那最后出队的节点就变成了最底层最右边的节点答案直接错。这类错误很难通过看代码发现因为语法、结构全对只有结果不对。我的经验是写完代码后哪怕不运行也要先拿一棵小树手动走一遍入队出队流程。DFS解法里常见的坑是depth传递错误。比如算完左子树后有人会粗心地在右子树调用时写成depth 2那深度就完全错乱了。另外递归里如果先更新result再判断depth max_depth会导致所有节点都更新一次结果最后答案变成最右边的一个节点而这个值毫无意义。还有一种隐蔽的错误在迭代式DFS里有人会在入栈时把(root, 1)写成(root, 0)然后更新条件用depth max_depth导致根节点的深度和其他节点不一致。这属于定义混乱问题务必在写代码前想清楚根节点的深度究竟是什么不要写到一半再猜。4.3 边界情况处理全清单写任何二叉树题目边界情况的测试用例都是必不可少的。针对513这道题我整理了一个最小测试清单测试场景树的结构期望输出要验证的点单节点[1]1基础正确性答案不能是null纯左链[1,2,3]2是1的左子3是2的左子3最底层最左的递归更新逻辑纯右链[1,null,2,null,3]3最左路径不存在时能否正确处理左右子树高度相等[1,2,3,4,5,6,7]4同层多节点时取第一个左子树更浅右子树更深自定义形状右子树最深层的左节点深度优先的真正含义特别要测纯右链这种反直觉场景它最容易暴露一路向左的错误思路。还有就是最后一层只有一个节点的情况比如[1,2,3,4,5,6,null]最底层只有6一个节点答案就是6。这些用例我在本地跑的时候统统走一遍确保万无一失再提交基本都是一次过。5. 从513题延伸的面试知识网络5.1 二叉树遍历的变式题目513不是孤立的一道题它处于一个庞大的二叉树遍历变式题家族中。刷完513如果顺着这道题把相关的题目都走一遍你会有一种打通了任督二脉的感觉。LeetCode 199 二叉树的右视图BFS层序遍历每层最后一个节点就是右视图看到的节点。和513的每层第一个节点形成镜像对照。LeetCode 102 二叉树的层序遍历原汁原味的层序遍历需要把每层节点装进二维数组。513的size len(queue)手法在这里就是标配。LeetCode 107 二叉树的层序遍历II从叶子层往上遍历本质就是层序遍历结果反转。LeetCode 103 二叉树的锯齿形层序遍历偶数行从右往左奇数行从左往右。这里面的方向切换和513的从右到左思路有异曲同工之处。LeetCode 515 在每个树行中找最大值层序遍历过程中维护每一层的最大值和513维护每层第一个节点是同一种操作范式。把这些题放到一起刷你会发现它们的核心骨架惊人地相似都是遍历整棵树同时在遍历过程中维护某种层维度上的信息。理解了这层共性你就不需要死背每道题的代码而是掌握了这一类题的通法——BFS天然适合按层处理DFS天然适合追踪深度信息。5.2 看到这道题应该联想到的知识点如果面试官给出513这道题他真正想考察的其实是这一系列东西第一二叉树的基本遍历。BFS和DFS都必须信手拈来递归和迭代两种形态至少要会一种。从实际面试经验看很多候选人BFS背得很熟但让他不用队列写一个DFS就卡壳这属于基本功不全面。第二状态维护。这道题表面上只是找最底层最左边的节点但在遍历过程中维护max_depth和result两个状态变量是一种非常经典的边走边记思维。这种思维在后续刷二叉树路径和、二叉树最大宽度、二叉树最近公共祖先时都会反复用到。第三递归的本质。如果你选择DFS解法面试官一定会追问递归的深度问题和空间复杂度。这要求你不仅会写代码还理解递归调用栈的运作机制知道极端情况下比如链表化二叉树10000个节点递归可能栈溢出从而引出迭代写法。第四代码的鲁棒性。空树怎么办一个节点怎么办全左子树和全右子树怎么办这些边界情况能反映出候选人考虑问题是否全面是面试评分的重要参考维度。5.3 一道题带出的LeetCode刷题方法论聊完513本身我想多说一点关于刷题方法论的体感。很多人刷LeetCode是按顺序从1刷到513刷到后面忘前面半途放弃。我自己的经验是按题型图谱刷而不是按题号刷。二叉树遍历这一簇从102、107、103、199、515、513这样串下来每道题都是在前一道题基础上加一个小变化难度曲线平滑成就感强知识留存率也比盲目刷高很多。拿513说如果你先掌握了102的层序遍历理解size len(queue)的每一层分界再看到513时你能立刻想到这不就是在每一层记录第一个节点吗如果你先掌握了二叉树最大深度的DFS写法再看到513时你能立刻想到这不就是多维护一个最左节点吗。这种知识迁移能力才是刷题真正要训练的东西。我在带人刷题时还发现一个规律中等难度的二叉树题80%都是在这两个基本遍历框架上做文章。所以不要嫌513简单把这道题吃透胜过囫囵吞枣刷十道难题。你可以试着把513的实现默写三遍BFS从左到右版、BFS从右到左版、DFS递归版。每遍之间隔半天看看自己能不能不看答案写出来。如果三遍都能流畅写对说明这个知识点是真的入脑了而不是停留在看懂了的错觉层面。我在实际刷题中还有一个习惯每次用不同解法写完后会在注释里记录每种解法的关键思路以及如果面试官追问性能瓶颈该怎么答。比如这道题我会在文件顶部写下BFS空间O(n)时间O(n)DFS递归栈O(h)最坏O(n)。这些小笔记在秋招冲刺复习时价值极高半小时就能过完一整册重点题不需要重新读题重做。 LeetCode 513：二叉树遍历核心考点，BFS与DFS精讲
1. 从一道题看二叉树遍历的核心考点1.1 LeetCode 513到底在考什么LeetCode 513这题题目全称叫找树左下角的值对应的英文是Find Bottom Left Tree Value。很多第一次刷到这道题的人第一眼看到左下角三个字会下意识以为要一路向左走到最底层。等真正动手写代码才发现题目要求的是先找到二叉树最深的那一层再取这一层最左侧节点的值。先深后左优先级一反过来思路就完全不一样了。这道题给定的是一个非空二叉树要求返回最底层最左边节点的值。官方难度定的是中等但坦白讲这道题在中等里算是非常友好的那一档。它不涉及什么复杂的算法技巧本质就是二叉树遍历的两种基本功——广度优先搜索BFS和深度优先搜索DFS。之所以被定为中等是因为它把层数和左右顺序这两个维度叠加在一起考察你对遍历过程的理解是否够细。我刷题这些年越来越觉得513这类题是很好的试金石。它不像动态规划那样需要大量练习才能建立感觉也不像并查集那样需要预先了解数据结构它就是纯粹的二叉树遍历但恰恰是这种基础题最能看出一个人对BFS和DFS的理解是背模板还是真懂了。你要是能把这道题从里到外讲明白二叉树遍历这块的基础基本就夯实了。1.2 为什么左下角是个容易踩坑的概念先说一个我见过的经典翻车现场。有同学一上来就写递归每次都先往左子树走一路走到叶子节点然后把结果返回。遇到下面这棵树时会直接出错1 / \ 2 3 / / \ 4 5 6 \ 7最底层是深度4那一层节点只有7一个所以左下角的值是7。但如果只是一路向左走到的是4显然不对。因为题目要的是最深的层而不是最靠左的路径。另一个容易混淆的点是左下角和最底层最左边的区别。有的树最底层只有一个节点那它既是唯一的节点也是最左边的节点有的树最底层有多个节点这时候要的是这一层第一个最左边那个。比如下面这棵1 / \ 2 3 / \ \ 4 5 6 \ 7最底层是深度4只有7一个节点所以答案是7。再比如1 / \ 2 3 / \ / \ 4 5 6 7最底层是深度3这一层有4、5、6、7四个节点左下角是4。这些例子说明一个核心原则先确定最深这个约束再考虑最左这个约束两个条件缺一不可顺序也不能颠倒。理解了这一点这道题的解题方向就清晰了——本质上就是一次完整遍历在遍历过程中同时维护当前深度和该深度下的最左节点这两个信息。2. 解法一BFS层序遍历的两种思路2.1 从右到左的反向思维BFS层序遍历大家都很熟用队列先入根节点然后一层一层往外扩展。但513这题如果用BFS有一个非常巧妙的切入点——让每一层的节点按照从右到左的顺序入队这样最后一个出队的节点一定是最底层最左边的节点。这个思路妙在哪里我们来推演一遍。标准层序遍历是从左往右假设当前层有[a, b, c]三个节点按顺序处理后它们的孩子节点会依次进入队列。如果我们改成从右往左处理也就是先处理c、再处理b、最后处理a那么下一层的节点入队顺序就变成了右边的孩子先入左边的孩子后入。队列是先进先出的所以越靠左的节点越晚出队。当我们把整棵树完整遍历完队列清空的那一刻最后一个出队的节点是什么是最底层最后入队的那一批节点中最后出队的一个。因为每一层都是从右往左处理所以最底层最后出队的那个节点恰好就是这一层最左边的节点。整个推导环环相扣一句话总结就是反向层序遍历最后出队的节点就是答案。from collections import deque def findBottomLeftValue(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核心就三行逻辑出队、右孩子入队、左孩子入队。循环结束后node变量指向的就是最后一个出队的节点。我第一次看到这个写法的时候愣了一下因为它短得不像一道中等题。但仔细想想这正是BFS特性的精准利用——你不需要手动记录层数不需要在每一层结束时做判断甚至不需要额外变量保存答案队列本身帮你完成了所有工作。2.2 从左到右记录每层首个节点如果你觉得从右到左的写法有点炫技那从左到右的传统层序遍历其实更符合直觉。思路很简单逐层遍历记录每一层第一个出队的节点遍历结束后最后一次记录的节点就是最底层的最左节点。from collections import deque def findBottomLeftValue(root): 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这里有个关键操作在每一层开始之前先用size len(queue)记录当前层的节点数然后只循环size次。为什么要这样因为队列在遍历过程中会不断加入下一层的节点如果不固定循环次数你就分不清哪些是当前层的节点、哪些是下一层的。size相当于给这一层画了一条分界线这是层序遍历的经典手法在二叉树右视图、锯齿形遍历等题目里都会用到。i 0判断的是当前层第一个出队的节点。因为我左孩子先入队左孩子比右孩子先出队所以第一个出队的天然就是最左节点。整个遍历结束后leftmost被每一层的第一个节点依次覆盖最终留下的一定是最后一层的第一个节点。这个写法思想上更直白代码也容易记适合面试时作为首选方案讲给面试官听。我个人的习惯是面试优先讲从左到右的笨办法讲清楚思路后再提一嘴从右到左的巧妙写法。这样既展示了基础功又体现了你对BFS理解的深度。2.3 BFS解法的复杂度分析两种BFS写法的时间复杂度和空间复杂度完全一致。时间复杂度是O(n)因为每个节点恰好入队一次、出队一次。空间复杂度是O(n)因为队列中最多同时存在某一层的全部节点满二叉树的最底层节点数大约是n/2所以数量级就是O(n)。这道题n的范围一般题目里会给出通常是[1, 10^4]级别完全不构成压力。但这个复杂度分析不是走过场面试官可能会追一句你的BFS空间复杂度能不能优化。从右到左的写法其实在空间上没有任何额外优化它还是存了所有节点和从左到右的写法空间复杂度相同。真正能优化空间的是后续要讲的DFS写法递归栈的深度是O(h)h是树高在极端情况下才退化成O(n)。还有一个细节值得注意从右到左的写法里queue.popleft()用的是双端队列的左侧弹出操作底层是链表实现的O(1)复杂度。你要是用Python的list模拟队列用pop(0)弹左侧元素那是O(n)的一旦数据量上来性能差距会非常明显。这也是为什么所有BFS代码都默认用from collections import deque这个习惯在刷题时要养成。3. 解法二DFS递归如何追踪深度3.1 深度优先的核心逻辑如果你对BFS的层序遍历已经炉火纯青那DFS解法的思路也一通百通。DFS的核心思想是带着当前深度去遍历每当发现一个节点比之前记录的最大深度更深就把这个节点的值记为答案因为是先遍历左子树再遍历右子树所以同一深度下第一次更新的节点一定是最左边的。这里面的关键在于更新时机。不是遇到新节点就更新而是只在depth maxDepth时才更新。这么做的好处是同一层的节点只有第一个被访问到的也就是最左边的会触发更新后面的节点深度和maxDepth相等不会覆盖之前的答案。比如在最底层有[4, 5, 6, 7]四个节点DFS先遍历到4此时深度是3大于之前记录的maxDepth2所以maxDepth更新为3答案更新为4。紧接着遍历到5深度也是3但不大于maxDepth3所以不更新。6和7同理。最终答案就是4完美命中最底层最左边。def findBottomLeftValue(root): max_depth -1 result root.val def dfs(node, depth): nonlocal max_depth, result if node is None: return if depth max_depth: max_depth depth result node.val dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return result这段代码里nonlocal是关键Python中嵌套函数要修改外层函数的变量必须用nonlocal声明否则会报错或者产生局部变量遮蔽。很多人在IDE里写这段代码时遇到UnboundLocalError十有八九是忘了这一行。3.2 递归代码的关键细节递归解法里有几个细节点睛之笔逐一说一下。第一max_depth的初始值设为-1。为什么不设为0因为根节点的深度是00 -1成立所以根节点一定会触发第一次更新把result初始化为根节点的值。如果你把max_depth设为0那当根节点深度为0时0 0不成立result就不会被初始化。当然你可以在外层直接把result设为root.val来绕开这个问题但这样代码就多了一行也少了那种所有节点都通过统一逻辑更新的优雅感。第二递归时depth 1而不是depth。函数式传参不修改当前变量的值每条递归路径都有自己独立的depth副本互不干扰。这是递归里非常基础但重要的概念——参数传递是值传递每个栈帧里的depth只代表当前路径的深度。第三先递归左子树再递归右子树。顺序能反吗如果先右后左那同一层第一个被访问到的节点就是最右节点答案就错了。所以左右顺序不能调换。这也是利用DFS天然顺序的一个典型体现。第四为什么这个解法能处理只有一个节点的树假设树只有一个根节点DFS进入后depth0 -1成立result被设为根节点值然后左右子树都是空直接返回。整个流程没有访问任何其他节点结果就是根节点值逻辑自洽。DFS在空间上比BFS有优势递归栈的深度等于树高h最坏情况下树退化成链表时是O(n)平均情况下是O(log n)。如果你在面试中被追问能不能用O(height)空间解决DFS就是你要给出的答案。3.3 迭代式DFS栈的写法如果不想写递归或者怕递归深度超过Python默认的1000层限制可以改成手动用栈模拟DFS。但这里有个小陷阱栈是后进先出的你要保证左子树先被处理就必须让右子树先进栈这样左子树才会后进先出地先被弹出。def findBottomLeftValue(root): max_depth -1 result root.val stack [(root, 0)] while stack: node, depth stack.pop() if node is None: continue if depth max_depth: max_depth depth result node.val # 栈是LIFO右先入栈左后入栈弹出时左先出 if node.right: stack.append((node.right, depth 1)) if node.left: stack.append((node.left, depth 1)) return result有人可能会问这里和递归的顺序还能保持一致吗能。递归的本质就是系统栈我们手动用栈模拟的是同一套逻辑。right先入栈、left后入栈弹出的顺序就是left先出、right后出和递归版本先处理左子树完全一致。代码里我还特意做了一个小优化——node为空时直接用continue跳过省得在入栈时就做大量非空判断。迭代写法在刷题时不一定用得上但它体现了你对递归本质的理解面试官如果问递归会不会爆栈怎么解决你能立刻给出这个方案会比只说把递归改成迭代更有说服力。4. 常见误区与调试技巧4.1 概念混淆左下角不是左子树路径这道题错得最多的认知误区就是把左下角理解成从根节点一路往左走到最底。我见过有人用while root.left: root root.left这种代码来解还觉得自己思路很简洁。这种解法在恰好最左路径就是最深路径的树上碰巧能过换个形状就立刻失效。举一个极端的例子1 \ 2 \ 3 \ 4这棵树全是右子树一路往左走根本走不动。但它的最底层是深度3那一层只有节点4所以左下角是4。如果按一路向左的思路你甚至找不出任何左孩子结果就是初始值答案整个漏掉。这种反例在面试时很有用你可以现场画给面试官看既展示了边界思维也证明你真的理解了题意。另一个相关误区是混淆深度和高度的概念。有的教材里根节点深度是1有的定义是0。代码里把根节点的深度定义成多少直接影响了max_depth的初始值和更新逻辑。只要自己在代码里保持一致两种定义都能写对但面试答到复杂度或状态转移时口径一定要统一。我习惯用0作为根节点深度这样很多二叉树公式比如完美二叉树第k层节点数是2^k更顺。4.2 队列/栈操作中的细节坑BFS解法里最容易犯的一个错误是入队顺序写反。你如果在从右到左的写法里把左孩子先入队、右孩子后入队那最后出队的节点就变成了最底层最右边的节点答案直接错。这类错误很难通过看代码发现因为语法、结构全对只有结果不对。我的经验是写完代码后哪怕不运行也要先拿一棵小树手动走一遍入队出队流程。DFS解法里常见的坑是depth传递错误。比如算完左子树后有人会粗心地在右子树调用时写成depth 2那深度就完全错乱了。另外递归里如果先更新result再判断depth max_depth会导致所有节点都更新一次结果最后答案变成最右边的一个节点而这个值毫无意义。还有一种隐蔽的错误在迭代式DFS里有人会在入栈时把(root, 1)写成(root, 0)然后更新条件用depth max_depth导致根节点的深度和其他节点不一致。这属于定义混乱问题务必在写代码前想清楚根节点的深度究竟是什么不要写到一半再猜。4.3 边界情况处理全清单写任何二叉树题目边界情况的测试用例都是必不可少的。针对513这道题我整理了一个最小测试清单测试场景树的结构期望输出要验证的点单节点[1]1基础正确性答案不能是null纯左链[1,2,3]2是1的左子3是2的左子3最底层最左的递归更新逻辑纯右链[1,null,2,null,3]3最左路径不存在时能否正确处理左右子树高度相等[1,2,3,4,5,6,7]4同层多节点时取第一个左子树更浅右子树更深自定义形状右子树最深层的左节点深度优先的真正含义特别要测纯右链这种反直觉场景它最容易暴露一路向左的错误思路。还有就是最后一层只有一个节点的情况比如[1,2,3,4,5,6,null]最底层只有6一个节点答案就是6。这些用例我在本地跑的时候统统走一遍确保万无一失再提交基本都是一次过。5. 从513题延伸的面试知识网络5.1 二叉树遍历的变式题目513不是孤立的一道题它处于一个庞大的二叉树遍历变式题家族中。刷完513如果顺着这道题把相关的题目都走一遍你会有一种打通了任督二脉的感觉。LeetCode 199 二叉树的右视图BFS层序遍历每层最后一个节点就是右视图看到的节点。和513的每层第一个节点形成镜像对照。LeetCode 102 二叉树的层序遍历原汁原味的层序遍历需要把每层节点装进二维数组。513的size len(queue)手法在这里就是标配。LeetCode 107 二叉树的层序遍历II从叶子层往上遍历本质就是层序遍历结果反转。LeetCode 103 二叉树的锯齿形层序遍历偶数行从右往左奇数行从左往右。这里面的方向切换和513的从右到左思路有异曲同工之处。LeetCode 515 在每个树行中找最大值层序遍历过程中维护每一层的最大值和513维护每层第一个节点是同一种操作范式。把这些题放到一起刷你会发现它们的核心骨架惊人地相似都是遍历整棵树同时在遍历过程中维护某种层维度上的信息。理解了这层共性你就不需要死背每道题的代码而是掌握了这一类题的通法——BFS天然适合按层处理DFS天然适合追踪深度信息。5.2 看到这道题应该联想到的知识点如果面试官给出513这道题他真正想考察的其实是这一系列东西第一二叉树的基本遍历。BFS和DFS都必须信手拈来递归和迭代两种形态至少要会一种。从实际面试经验看很多候选人BFS背得很熟但让他不用队列写一个DFS就卡壳这属于基本功不全面。第二状态维护。这道题表面上只是找最底层最左边的节点但在遍历过程中维护max_depth和result两个状态变量是一种非常经典的边走边记思维。这种思维在后续刷二叉树路径和、二叉树最大宽度、二叉树最近公共祖先时都会反复用到。第三递归的本质。如果你选择DFS解法面试官一定会追问递归的深度问题和空间复杂度。这要求你不仅会写代码还理解递归调用栈的运作机制知道极端情况下比如链表化二叉树10000个节点递归可能栈溢出从而引出迭代写法。第四代码的鲁棒性。空树怎么办一个节点怎么办全左子树和全右子树怎么办这些边界情况能反映出候选人考虑问题是否全面是面试评分的重要参考维度。5.3 一道题带出的LeetCode刷题方法论聊完513本身我想多说一点关于刷题方法论的体感。很多人刷LeetCode是按顺序从1刷到513刷到后面忘前面半途放弃。我自己的经验是按题型图谱刷而不是按题号刷。二叉树遍历这一簇从102、107、103、199、515、513这样串下来每道题都是在前一道题基础上加一个小变化难度曲线平滑成就感强知识留存率也比盲目刷高很多。拿513说如果你先掌握了102的层序遍历理解size len(queue)的每一层分界再看到513时你能立刻想到这不就是在每一层记录第一个节点吗如果你先掌握了二叉树最大深度的DFS写法再看到513时你能立刻想到这不就是多维护一个最左节点吗。这种知识迁移能力才是刷题真正要训练的东西。我在带人刷题时还发现一个规律中等难度的二叉树题80%都是在这两个基本遍历框架上做文章。所以不要嫌513简单把这道题吃透胜过囫囵吞枣刷十道难题。你可以试着把513的实现默写三遍BFS从左到右版、BFS从右到左版、DFS递归版。每遍之间隔半天看看自己能不能不看答案写出来。如果三遍都能流畅写对说明这个知识点是真的入脑了而不是停留在看懂了的错觉层面。我在实际刷题中还有一个习惯每次用不同解法写完后会在注释里记录每种解法的关键思路以及如果面试官追问性能瓶颈该怎么答。比如这道题我会在文件顶部写下BFS空间O(n)时间O(n)DFS递归栈O(h)最坏O(n)。这些小笔记在秋招冲刺复习时价值极高半小时就能过完一整册重点题不需要重新读题重做。