LogicStack-LeetCode 题解精读：513. 找树左下角的值——BFS 层序与 DFS 深度优先双解法剖析

教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南围绕「刷穿 LeetCode」系列中 513. 找树左下角的值中等 一题展开核心任务是给定一棵二叉树的根节点root找出该二叉树最底层、最左边节点的值。读者读完本文后将掌握两种经典实现——按层推进的 BFS 层序遍历与记录最大深度的 DFS 深度优先遍历理解二者各自的正确性依据、代码模板与复杂度特征并能在 LeetCode 与本地环境中直接调试运行。题目理解什么才是最底层最左边题目要求返回二叉树最底层深度最大的一层中最左边节点的值假设二叉树至少有一个节点。示例 1输入: root [2,1,3] 输出: 1该树共两层第二层只有1和3两个节点最左边的是1因此返回1。示例 2输入: root [1,2,3,4,null,5,6,null,null,7] 输出: 7该树最深一层是第 4 层其中只有节点7所以返回7。注意这里最左边是相对同一层而言的如果最深层有多个节点返回其中位置最靠左的一个若最深层只有一个节点则直接返回该节点。题目提示明确了两点约束二叉树节点个数的范围是 $[1, 10^4]$即树非空且规模适中节点值范围是 $-2^{31} \le Node.val \le 2^{31} - 1$即节点值可能为负数。这一数据范围意味着两种 $O(n)$ 解法都能轻松通过而节点值可正可负也提醒我们在求每层极值类问题中初值不能想当然地设为0。该题被收录在仓库的 BFS 专题索引 与 DFS 专题索引 中作为树的遍历Tag 下的中等题推荐指数四星是层序遍历与深度优先遍历的典型练兵场。解法一BFS 层序遍历——每层首节点即左下角核心思路使用 BFS 进行层序遍历队列中每次恰好存放一整层的节点。处理某一层时记录该层队首节点的值作为候选答案ans然后把这一层的所有节点依次出队并将其非空左右孩子入队。当 BFS 全部结束时ans自然就是最后一层最靠左的节点。为什么队首节点就是该层最左因为 BFS 按层推进、层内按从左到右的顺序入队根节点入队后先入队左孩子再入队右孩子因此每一层在队列中的顺序严格保持从左到右。层与层之间由sz当前层节点数划界处理完一层后队列剩余的部分恰好是下一层的全部节点。Java 实现class Solution { public int findBottomLeftValue(TreeNode root) { DequeTreeNode d new ArrayDeque(); d.addLast(root); int ans 0; while (!d.isEmpty()) { int sz d.size(); ans d.peek().val; while (sz-- 0) { TreeNode poll d.pollFirst(); if (poll.left ! null) d.addLast(poll.left); if (poll.right ! null) d.addLast(poll.right); } } return ans; } }C 实现class Solution { public: int findBottomLeftValue(TreeNode* root) { dequeTreeNode* d; d.push_back(root); int ans 0; while (!d.empty()) { int sz d.size(); ans d.front()-val; while (sz-- 0) { TreeNode* poll d.front(); d.pop_front(); if (poll-left ! nullptr) d.push_back(poll-left); if (poll-right ! nullptr) d.push_back(poll-right); } } return ans; } };Python 实现class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) - int: d deque([root]) ans 0 while d: sz len(d) ans d[0].val while sz 0: poll d.popleft() if poll.left: d.append(poll.left) if poll.right: d.append(poll.right) sz - 1 return ansTypeScript 实现function findBottomLeftValue(root: TreeNode | null): number { const d [root]; let ans 0; while (d.length 0) { const sz d.length; ans d[0].val; for (let i 0; i sz; i) { const poll d.shift()!; if (poll.left) d.push(poll.left); if (poll.right) d.push(poll.right); } } return ans; };关键细节先记录再出队ans d.peek().val必须在处理整层节点之前执行因为出队过程中队首会不断变化用sz固定本层节点数内层循环只弹出sz个节点保证新入队的下一层节点不会在本轮被错误处理入队顺序固定为先左后右这是层内从左到右有序性的来源也是本题 BFS 解法的正确性基石。复杂度时间复杂度$O(n)$每个节点恰好入队、出队一次空间复杂度最坏情况下所有节点位于同一层如完全二叉树的最底层队列同时容纳 $n$ 个节点复杂度为 $O(n)$。解法二DFS 深度优先——先左后右 记录最大深度核心思路BFS 天然按层推进DFS 则纵向深入。DFS 版本的关键洞察是只要每次优先遍历左子树那么第一次搜索到某个更深深度depth时访问到的必然是当前深度的最左节点。实现上维护两个全局变量max当前已到达的最大深度与ans当前最大深度对应的最左节点值。从根节点以深度1开始 DFS每次进入节点时若depth max说明这是第一次触达更深的层级此时该节点就是这一新层级的最左节点因为遍历顺序是先左后右于是更新max与ans随后继续递归左子树、右子树。为什么第一次到达的更深层节点必然最左DFS 的访问顺序决定了在深度d的所有节点中最左边的节点一定是最先被访问到的那个——递归先完整走完左分支才会回到上一层去访问右侧分支。因此深度刷新时刻捕捉到的节点恰好是该深度最左的节点而随着 DFS 推进max会不断被刷新到树的最大深度最终ans即为最底层最左节点的值。Java 实现class Solution { int max, ans; public int findBottomLeftValue(TreeNode root) { dfs(root, 1); return ans; } void dfs(TreeNode root, int depth) { if (root null) return ; if (depth max) { max depth; ans root.val; } dfs(root.left, depth 1); dfs(root.right, depth 1); } }C 实现class Solution { public: int maxv 0, ans 0; int findBottomLeftValue(TreeNode* root) { dfs(root, 1); return ans; } void dfs(TreeNode* root, int depth) { if (!root) return; if (depth maxv) { maxv depth; ans root-val; } dfs(root-left, depth 1); dfs(root-right, depth 1); } };Python 实现class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) - int: self.maxv, self.ans 0, 0 self.dfs(root, 1) return self.ans def dfs(self, root: TreeNode, depth: int) - None: if not root: return if depth self.maxv: self.maxv depth self.ans root.val self.dfs(root.left, depth 1) self.dfs(root.right, depth 1)TypeScript 实现let max, ans; function dfs(root: TreeNode | null, depth: number): void { if (!root) return; if (depth max) { max depth; ans root.val; } dfs(root.left, depth 1); dfs(root.right, depth 1); } function findBottomLeftValue(root: TreeNode | null): number { max 0; ans 0; dfs(root, 1); return ans; };关键细节判断条件是depth max而非只有首次到达更深的层级才更新答案同深度的节点即使更靠右也不能覆盖已记录的最左值必须先递归左子树若调换左右递归顺序捕捉到的将是该层最右节点答案就错了根节点深度从1起算与层号定义保持一致max初始为0保证根节点必然触发首次更新。复杂度时间复杂度$O(n)$每个节点访问一次空间复杂度最坏情况下树退化成链递归深度为 $n$复杂度为 $O(n)$。两种解法对比与选型维度BFS 层序DFS 深度优先核心机制队列按层推进每层队首即最左先左后右递归首次触达新深度即最左正确性依据层内入队顺序从左到右访问顺序保证最左节点先被访问额外状态无仅队列与答案变量全局max与ans时间/空间$O(n)$ / $O(n)$$O(n)$ / 最坏 $O(n)$链状树递归栈空间实际表现与树宽相关与树高相关完全二叉树下 BFS 队列可能更宽DFS 栈深更浅两者复杂度量级一致实际选择取决于出题场景与个人习惯BFS 思路直观、无需全局变量DFS 代码更短、在找最左/最右/最深类问题上具有统一模板价值。从本题延伸仓库中的层序遍历问题家族本题的核心模板——用sz固定一层节点数逐层处理——在仓库中广泛复用可作为通解模板记忆。同类问题包括在每个树行中找最大值中等BFS 版本把记录队首换成维护本层最大值DFS 版本则用哈希表按深度记录最大值是本题取每层首节点思路的同构变体最大层内元素和中等逐层累加元素和并维护最大层号和层深仅把取最左换成求和取最大层数最深叶子节点的和中等用哈希表按深度累计和BFS 与 DFS 双解法均给出与本题目关注最深一层的诉求一致。这几篇题解连同本题一起构成了层序/深度优先遍历系列的完整方法论凡是涉及某一层的最值、首个、末个、求和的问题都可以用BFS 逐层处理或DFS 深度状态两套模板秒杀。相关题解在 BFS 专题 与 DFS 专题 中按 Tag 汇总可对照学习。本地调试与提交建议以上四种语言代码均可直接粘贴至 LeetCode 对应编辑器中提交运行该题在 LeetCode 上编号 513。本地调试时可按如下方式快速验证Pythonfrom collections import deque按题目示例构造树节点并调用findBottomLeftValue核对输出1与7TypeScript在 Node.js 环境用ts-node或直接编译运行注意TreeNode需自行定义{ val, left, right }Java / C在 IDE 中定义TreeNode结构体/类粘贴Solution后编写main构造两个示例输入进行断言。务必覆盖两类边界用例单节点树返回根节点值与最深一层仅一个节点如示例 2返回7这两类用例能同时校验 BFS 的层内顺序与 DFS 的深度更新逻辑是否正确。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode 513 找树左下角的值层序遍历BFS与深度优先DFS双解法精讲LeetCode 513 找树左下角的值层序遍历BFS与深度优先DFS双解法精讲 导读 本文以 leetcode 题解仓库中的 513 找树左下角的值文档教程知识库LogicStack-LeetCode 题解199. 二叉树的右视图——BFS 层序与 DFS 优先遍历双解法全解LogicStack LeetCode 题解199. 二叉树的右视图——BFS 层序与 DFS 优先遍历双解法全解 导读 本文是「宫水三叶的刷题日记」刷穿 L教程文档LeetCode-Book 精讲LCR 175 计算二叉树的深度 —— 后序 DFS 与层序 BFS 双解法全解析LeetCode Book 精讲LCR 175 计算二叉树的深度 —— 后序 DFS 与层序 BFS 双解法全解析 本篇技术指南以《LeetCode Book示例工程上一篇autoskills Cloudflare Tunnel 实战手册常见故障排查、限制边界与生产级最佳实践下一篇三步打造你的私有AI知识库AnythingLLM全栈解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考