教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本篇是 InterviewGuide阿秀的学习笔记「精选力扣 300 道算法题」深度优先搜索DFS分类下的经典入门题解完整讲解如何求解二叉树的最大深度从最直白的条件分支递归到更简洁的递归变种再到可防止调用栈溢出的 BFS 层序迭代三种思路并延伸对比仓库中同源的最小深度、剑指 Offer 同题等训练题目帮助校招/社招求职者一次吃透「树的深度」这一高频考点。题目回顾什么是二叉树的最大深度原题104. 二叉树的最大深度难度简单。给定一个二叉树找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明叶子节点是指没有子节点的节点。示例给定二叉树[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7返回它的最大深度3。从示例可以直观看出根节点3到叶子节点15或7的路径为3 - 20 - 15共 3 个节点因此最大深度为 3。这里要特别留意题目中路径上的节点数这一表述——如果理解成边数答案会偏差 1这是面试中很容易踩的细节。这道题之所以被放在 DFS深度优先搜索分类下是因为它的天然解法就是沿着一条路径走到底再回溯一棵树的最大深度等于1 max(左子树最大深度, 右子树最大深度)空树深度为 0。该递推式本身就是 DFS 后序遍历的形态。仓库中的原题解笔记位于 104.二叉树的最大深度其所属的 DFS 分类索引见 13-DFS 目录。解法一条件分支递归直译递归思路原笔记给出的第一版写法是最贴近直觉的先处理空节点然后按左右孩子是否存在分情况递归。如果左右孩子都存在取两者深度较大值加 1如果只有右孩子则只递归右子树否则递归左子树。class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; if (root-left root-right) return 1 max(maxDepth(root-right), maxDepth(root-left)); if (!root-left) return 1 maxDepth(root-right); else return 1 maxDepth(root-left); } };原笔记记录了作者当时在 LeetCode 上的提交数据执行用时 20 ms击败 19.82% 的 C 提交内存消耗 20.5 MB击败 5.06% 的提交。需要注意这类击败百分比是提交时刻的快照随平台数据与测试用例变化会波动参考价值在于相对趋势而非绝对值。这段代码逻辑正确但存在明显冗余三种分支最终都收敛到1 某子树深度的形式完全可以用一个max统一表达不必显式判断左右孩子是否存在。这也是它耗时偏高的原因之一——分支判断多了代码路径更长。该解法与仓库中 面试题55-I.二叉树的深度 给出的代码完全一致印证了剑指 Offer 同题与主站 104 题是同一道题该文档中明确标注本题与主站 104 题相同。解法二递归变种更简洁的写法针对解法一的冗余原笔记给出了精简版空节点返回 0否则分别求出左右子树的深度并加 1最后取较大值。int maxDepth(TreeNode* root) { if (!root) return 0; int left_depth maxDepth(root-left) 1, right_depth maxDepth(root-right) 1; return max(left_depth, right_depth); }原笔记记录其提交数据为执行用时 12 ms击败 73.48% 的 C 提交内存消耗 20.7 MB击败 5.14% 的提交。相比解法一代码量大幅缩减且思路更加清晰递归基root为空时返回 0空树深度为 0递推关系当前节点的深度 左右子树深度中的较大值 1由于maxDepth(root-left)已经隐含了1之前对空子树返回 0 的处理所以代码里不需要任何分支判断。两种递归写法的时间复杂度都是 O(n)n 为节点数每个节点恰好访问一次但解法二在常量系数上更优且更符合分治的思维范式——先解决子问题左右子树的深度再合并出当前问题的答案。这也是面试时更推荐优先写出的版本。解法三BFS 层序迭代防止爆栈递归虽然简洁但当二叉树退化为一条链例如只有左孩子的极端树形时递归调用栈深度会达到 n在节点规模很大时可能触发栈溢出爆栈。原笔记给出的第三版解法改用 BFS 队列迭代从根本上规避递归栈问题int maxDepth(TreeNode* root) { if (!root) return 0; int max_dept 0; queuepairTreeNode*, int q; q.push({root, 1}); while (!q.empty()) { TreeNode* curr_node q.front().first; int curr_dept q.front().second; q.pop(); if (curr_node) { max_dept max(max_dept, curr_dept); q.push({curr_node-left, curr_dept 1}); q.push({curr_node-right, curr_dept 1}); } } return max_dept; }原笔记记录其提交数据为执行用时 12 ms击败 73.48% 的 C 提交内存消耗 20.8 MB击败 5.14% 的提交。该实现的核心思想是在队列元素中携带深度信息队列元素类型为pairTreeNode*, int第一个分量是节点指针第二个分量是该节点所处的深度根节点以深度 1 入队每次弹出队首元素用max_dept max(max_dept, curr_dept)持续更新已到达的最大深度无论左右孩子是否为nullptr都直接入队并在取出节点时用if (curr_node)跳过空节点——这样写的好处是无需在入队前做空指针判断逻辑更统一代价是队列中会短暂混入空指针元素可以推断对空间占用有轻微增加但不影响正确性。另外pair的初始化使用了 C11 的列表初始化语法{root, 1}与{curr_node-left, curr_dept 1}这是该题解适用于 C11 及以上标准的细节queue与pair分别来自标准库头文件queue与utility在力扣的评测环境中默认包含。空间复杂度对比递归 vs 迭代维度DFS 递归解法一/二BFS 层序解法三时间复杂度O(n)每个节点访问一次O(n)每个节点入队出队一次额外空间递归栈平均 O(log n)最坏 O(n)链状树队列最坏 O(n)满二叉树最后一层约 n/2 个节点栈溢出风险链状树深度极大时可能爆栈无递归栈天然规避可以看到二者在时间上都无法优于 O(n)必须遍历全部节点差别主要体现在空间分配的位置DFS 吃的是系统调用栈BFS 吃的是堆上动态分配的队列。对于节点总数上限高达 10000 的题目见仓库中 面试题55-I.二叉树的深度 的提示递归一般不会出问题但如果在生产环境或内存受限场景处理超大/极不平衡的树BFS 或显式栈的迭代写法是更稳妥的选择。同源题目联动仓库中的延伸训练「最大深度」绝不是孤立的一道题仓库的 DFS 分类下还沉淀了一系列同源题建议按如下顺序串联练习一通百通面试题55-I.二叉树的深度与本题完全相同的剑指 Offer 原题节点总数 10000可以把它当作 104 题的换皮复现用于检验自己是否真的掌握了递归写法——该文档给出的解法与本题解法一一致提交数据记录为 4 ms、击败 99.36% 的 C 提交。111.二叉树的最小深度最大深度的镜像题从找最远叶子变成找最近叶子。二者有一个关键差异容易写错最小深度不能简单地写成min(left, right) 1因为当某棵子树为空时最小深度应取另一棵非空子树的深度空子树路径不存在不能计为 0 参与min。仓库中的参考解法正是按这个思路对左右孩子是否为空做了分类讨论int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left !root-right) return 1; else if (!root-left root-right) return 1 minDepth(root-right); else if (!root-right root-left) return 1 minDepth(root-left); return min(minDepth(root-left), minDepth(root-right)) 1; }该文档记录的提交数据为执行用时 12 ms击败 85.15% 的 C 提交内存消耗 21.7 MB击败 5.11% 的提交。把 104 与 111 放在一起对比能一次性厘清最大/最小深度两种递推的边界条件。面试题04.02.最小高度树将树的深度知识点反向应用——给定升序数组构造高度最小的二叉搜索树BST。利用取中间元素为根、左右区间递归建树的 DFS 分治策略天然得到平衡树从而保证高度最小class Solution { private: TreeNode* dfs(vectorint nums, int l, int r) { if (l r) return NULL; int mid (l r) 1; TreeNode* root new TreeNode(nums[mid]); root-left dfs(nums, l, mid - 1); root-right dfs(nums, mid 1, r); return root; } public: TreeNode* sortedArrayToBST(vectorint nums) { if (nums.size() 0) return NULL; return dfs(nums, 0, nums.size() - 1); } };注意原笔记特别强调的细节入口处递归区间右边界必须是 nums.size() - 1 而不是 nums.size()否则 mid 可能越界访问。这道题与 104 题形成求深度 - 构造最小深度的双向闭环是面试官常用来考察是否真正理解树的高度的组合拳。以上四题均收录于仓库的 13-DFS 分类目录Easy 部分该分类是阿秀从近 600 道题中精选的 300 道刷题笔记之一整体使用指南见 精选力扣 300 道算法题总览。小结三种解法的适用场景条件分支递归解法一最贴合直觉的翻译式写法适合初学阶段理解递归边界但代码冗余、性能一般正式作答不推荐简洁递归变种解法二面试首选代码短、思路清晰展示对分治思想的掌握注意极端链状树的爆栈风险BFS 层序迭代解法三无递归栈风险适合超大输入与工程化场景同时复习了队列 层数的经典套路也是很多按层处理题如层序遍历的基础模板。最后记住一句话概括本题树的最大深度 1 max(左子树深度, 右子树深度)空树为 0。把这句话的递归形态与迭代形态都写熟练树的深度这一族题目最大深度、最小深度、最小高度树、判断平衡树就都能从容应对了。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐从终端驱动 GitHub Copilot独立 copilot CLI 的安装、认证与 Default / Plan / Auto 三种交互模式实战指南从终端驱动 GitHub Copilot独立 copilot CLI 的安装、认证与 Default / Plan / Auto 三种交互模式实战指南 Git教程Velero 最小权限 RBAC 配置指南从 cluster-admin 到受限权限的安全加固实践Velero 最小权限 RBAC 配置指南从 cluster admin 到受限权限的安全加固实践 导读 Velero 默认以 ClusterRole clu教程剑指Offer No38 二叉树的深度递归DFS与BFS迭代全解法剖析InterviewGuide 刷题笔记剑指Offer No38 二叉树的深度递归DFS与BFS迭代全解法剖析InterviewGuide 刷题笔记 本文是 InterviewGuide 仓库「文档教程知识库上一篇如何快速上手Zircolite10分钟掌握EVTX和Sysmon日志检测的完整指南下一篇小爱音箱怎么免费听全网歌XiaoMusic 三步在 NAS 上跑起来创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考