教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本篇是阿秀《InterviewGuide》精选力扣刷题笔记中深度优先搜索DFS分类下的经典二叉树题目解析。题目同时出现在《剑指 Offer》第 38 题二叉树深度与力扣主站 104 题二叉树的最大深度中是校招、社招笔试面试中出现频率极高的入门级 DFS 题目。读完本篇你将掌握求二叉树深度的递归后序遍历 DFS与迭代层序 BFS两种标准解法理解各自的复杂度特征与适用场景并能将其迁移到最小深度、平衡二叉树等衍生题目上。一、题目描述输入一棵二叉树的根节点求该树的深度。从根节点到叶节点依次经过的节点含根、叶节点形成树的一条路径最长路径的长度即为树的深度。示例给定二叉树[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7返回它的最大深度3。提示节点总数 10000注意本题与力扣主站104 题二叉树的最大深度完全相同只是题目编号与出处不同。仓库中该题的原始笔记位于 面试题55-I.二叉树的深度同题的另一个版本笔记为 104.二叉树的最大深度两者可对照阅读。二、思路一后序遍历式 DFS 递归原题官方解法这是原文档给出的解法。一棵树的深度可以递归地定义树为空时深度为 0否则深度 1 max(左子树深度, 右子树深度)。递归天然对应二叉树的自底向上后序遍历——先求左右子树的深度再在当前节点汇总。class Solution { public: int maxDepth(TreeNode* root) { if (!root ) return 0; if (root-left root-right) return 1max(maxDepth(root-right),maxDepth(root-left)); if (!root-left) return 1 maxDepth(root-right); else return 1maxDepth(root-left); } };逐行拆解代码分支语义if (!root) return 0;递归出口空节点叶子的 NULL 孩子深度为 0if (root-left root-right)左右孩子都存在取两侧递归结果较大者 1if (!root-left)只有右孩子或走到叶子时!root-left成立、root-right为 NULL直接下沉到右子树else return 1 maxDepth(root-left);只有左孩子直接下沉到左子树作者当时的提交记录为执行用时 4 ms击败 99.36% 的 C 提交内存消耗 20.8 MB击败 100.00% 的用户。需要说明的是LeetCode 的运行用时与内存会随提交环境、测试集规模波动同一段代码在仓库 104.二叉树的最大深度 中记录的提交结果为 20 ms / 19.82%因此这些百分比只代表当时单次提交的快照不必过度解读重点在于理解算法本身的复杂度。三、思路二统一模板的递归变种更简洁上面第一版解法把左右孩子是否存在拆成了多个分支判断。其实可以合并成一条更通用的递归式——先分别求左右子树深度再加 1 取最大值空节点天然返回 0无需单独讨论只有单孩子的情况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); }这个写法与《剑指 Offer》No38 中给出的二刷版本在逻辑上完全等价仓库见 38-剑指offer.mdint TreeDepth(TreeNode* pRoot) { if(pRoot nullptr) return 0; int leftDepth TreeDepth(pRoot-left); int rightDepth TreeDepth(pRoot-right); return 1 max(leftDepth,rightDepth); }两种写法的差异只在于1是加在递归返回值上还是加在局部变量上都属于后序遍历的 DFS。从可读性与面试手写速度来看统一模板更推荐因为它把深度递推公式表达得最直白。复杂度分析两种递归写法一致时间复杂度O(n)每个节点恰好被访问一次空间复杂度最坏情况O(n)——当二叉树退化为单链如每个节点只有左孩子时递归栈深度等于节点数平均/最好情况平衡树下为O(log n)。四、思路三BFS 层序遍历迭代版可防止爆栈递归在极端深链上可能栈溢出改用显式队列做层序遍历则完全不依赖系统调用栈。原文档虽只给了递归写法但仓库同题笔记 104.二叉树的最大深度 与 38-剑指offer.md 都补充了 BFS 版本这里一并收入int maxDepth(TreeNode* root) { if (!root) return 0; int max_dept 0; queuepairTreeNode*, int q; q.push({ root,1 }); // 根节点深度记为 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; }BFS 版的关键点队列元素是pairTreeNode*, int第二个字段记录该节点所在深度入队时深度加 1空节点也照常入队但在出队时用if (curr_node)跳过因此不需要在入队前判空逻辑更统一由于是逐层推进队内节点的深度单调递增所以max_dept也可以等价为最后一个出队节点的深度但用max维护更直观、更稳健。复杂度时间O(n)空间O(w)w为队列最大宽度平衡二叉树时约为O(n/2)量级。它的最大优势是把递归调用栈换成了堆上的队列在处理深度高达 10000 的单链树时不会爆栈。五、两种思路对比小结维度DFS 递归后序BFS 迭代层序核心思想深度 1 max(左右子树深度)逐层向下记录层号最大值时间复杂度O(n)O(n)空间复杂度最坏 O(n)链式树递归栈O(w)队列宽度最坏约 n/2代码量3~5 行最简洁约 10 行稍长风险点深链可能栈溢出无递归栈风险适用场景面试手写首选、代码量小生产环境 / 深树 / 防止爆栈对于本题节点总数 10000的限制两种写法在力扣环境下都能顺利通过但面试官常会追问如果树很深怎么办此时能答出 BFS 迭代方案会是明显的加分项。六、举一反三从最大深度到同族题目二叉树深度问题是一个小家族仓库的 DFS 分类目录见 13-DFS 目录中还收录了以下几道同族题目解法可以互相迁移1. 最小深度力扣 111——见 111.二叉树的最小深度。注意不能简单把max换成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; }2. 平衡二叉树剑指 Offer 55-II / No39——见 39-剑指offer.md。直接复用深度计算函数每个节点左右子树高度差不超过 1 即为平衡树。暴力写法是先求深度再判断会重复遍历改进写法是从下往上返回高度、发现不平衡立即返回 -1 剪枝int getDepth(TreeNode* node) { if (node nullptr) return 0; int leftDept getDepth(node-left); if (leftDept -1) return -1; int rightDept getDepth(node-right); if (rightDept -1) return -1; if (abs(leftDept - rightDept) 1) return -1; else return 1 max(leftDept, rightDept); } bool IsBalanced_Solution(TreeNode* pRoot) { if (pRoot nullptr) return true; return getDepth(pRoot) ! -1; }3. 最小高度树面试题 04.02——见 面试题04.02.最小高度树。这是深度的逆问题给定升序数组构造高度最小的二叉搜索树利用二分法取中点为根、递归构造左右子树即可每个节点深度贡献 1整棵树高度天然最小。七、本篇小结面试题55-I 力扣 104是二叉树类题目的地基题递归模板1 max(left, right)要能闭着眼睛写出来并讲清楚后序遍历的含义BFS 层序迭代版要会写、知道它能防爆栈作为深树场景的备选方案掌握深度这一基本量后最小深度、平衡二叉树判断等衍生题都可以建立在其上这是面试官最常做的由浅入深追问路线。仓库中同族题目的完整笔记可继续对照阅读104.二叉树的最大深度、111.二叉树的最小深度、剑指 Offer No38 二叉树深度、剑指 Offer No39 平衡二叉树以及 DFS 分类目录 中其余题目。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐剑指Offer No38 二叉树的深度递归DFS与BFS迭代全解法剖析InterviewGuide 刷题笔记剑指Offer No38 二叉树的深度递归DFS与BFS迭代全解法剖析InterviewGuide 刷题笔记 本文是 InterviewGuide 仓库「文档教程知识库面试题55-I. 二叉树的深度DFS 递归与 BFS 迭代两种解法详解InterviewGuide 力扣刷题笔记面试题55 I. 二叉树的深度DFS 递归与 BFS 迭代两种解法详解InterviewGuide 力扣刷题笔记 本文是 InterviewGuide 项文档教程知识库LeetCode 104. 二叉树的最大深度InterviewGuide 精选 DFS 刷题笔记C 递归与 BFS 全解LeetCode 104. 二叉树的最大深度InterviewGuide 精选 DFS 刷题笔记C 递归与 BFS 全解 本篇是 InterviewG教程上一篇如何零配置实现Jazzy文档自动化测试保障API文档一致性的完整方案下一篇librealsense RealSense 深度相机 SDK 部署调优实战手册从首帧到生产级创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 InterviewGuide 剑指 Offer 面试题55-I：二叉树的深度（LeetCode 104）——DFS 递归与 BFS 迭代全解
教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本篇是阿秀《InterviewGuide》精选力扣刷题笔记中深度优先搜索DFS分类下的经典二叉树题目解析。题目同时出现在《剑指 Offer》第 38 题二叉树深度与力扣主站 104 题二叉树的最大深度中是校招、社招笔试面试中出现频率极高的入门级 DFS 题目。读完本篇你将掌握求二叉树深度的递归后序遍历 DFS与迭代层序 BFS两种标准解法理解各自的复杂度特征与适用场景并能将其迁移到最小深度、平衡二叉树等衍生题目上。一、题目描述输入一棵二叉树的根节点求该树的深度。从根节点到叶节点依次经过的节点含根、叶节点形成树的一条路径最长路径的长度即为树的深度。示例给定二叉树[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7返回它的最大深度3。提示节点总数 10000注意本题与力扣主站104 题二叉树的最大深度完全相同只是题目编号与出处不同。仓库中该题的原始笔记位于 面试题55-I.二叉树的深度同题的另一个版本笔记为 104.二叉树的最大深度两者可对照阅读。二、思路一后序遍历式 DFS 递归原题官方解法这是原文档给出的解法。一棵树的深度可以递归地定义树为空时深度为 0否则深度 1 max(左子树深度, 右子树深度)。递归天然对应二叉树的自底向上后序遍历——先求左右子树的深度再在当前节点汇总。class Solution { public: int maxDepth(TreeNode* root) { if (!root ) return 0; if (root-left root-right) return 1max(maxDepth(root-right),maxDepth(root-left)); if (!root-left) return 1 maxDepth(root-right); else return 1maxDepth(root-left); } };逐行拆解代码分支语义if (!root) return 0;递归出口空节点叶子的 NULL 孩子深度为 0if (root-left root-right)左右孩子都存在取两侧递归结果较大者 1if (!root-left)只有右孩子或走到叶子时!root-left成立、root-right为 NULL直接下沉到右子树else return 1 maxDepth(root-left);只有左孩子直接下沉到左子树作者当时的提交记录为执行用时 4 ms击败 99.36% 的 C 提交内存消耗 20.8 MB击败 100.00% 的用户。需要说明的是LeetCode 的运行用时与内存会随提交环境、测试集规模波动同一段代码在仓库 104.二叉树的最大深度 中记录的提交结果为 20 ms / 19.82%因此这些百分比只代表当时单次提交的快照不必过度解读重点在于理解算法本身的复杂度。三、思路二统一模板的递归变种更简洁上面第一版解法把左右孩子是否存在拆成了多个分支判断。其实可以合并成一条更通用的递归式——先分别求左右子树深度再加 1 取最大值空节点天然返回 0无需单独讨论只有单孩子的情况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); }这个写法与《剑指 Offer》No38 中给出的二刷版本在逻辑上完全等价仓库见 38-剑指offer.mdint TreeDepth(TreeNode* pRoot) { if(pRoot nullptr) return 0; int leftDepth TreeDepth(pRoot-left); int rightDepth TreeDepth(pRoot-right); return 1 max(leftDepth,rightDepth); }两种写法的差异只在于1是加在递归返回值上还是加在局部变量上都属于后序遍历的 DFS。从可读性与面试手写速度来看统一模板更推荐因为它把深度递推公式表达得最直白。复杂度分析两种递归写法一致时间复杂度O(n)每个节点恰好被访问一次空间复杂度最坏情况O(n)——当二叉树退化为单链如每个节点只有左孩子时递归栈深度等于节点数平均/最好情况平衡树下为O(log n)。四、思路三BFS 层序遍历迭代版可防止爆栈递归在极端深链上可能栈溢出改用显式队列做层序遍历则完全不依赖系统调用栈。原文档虽只给了递归写法但仓库同题笔记 104.二叉树的最大深度 与 38-剑指offer.md 都补充了 BFS 版本这里一并收入int maxDepth(TreeNode* root) { if (!root) return 0; int max_dept 0; queuepairTreeNode*, int q; q.push({ root,1 }); // 根节点深度记为 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; }BFS 版的关键点队列元素是pairTreeNode*, int第二个字段记录该节点所在深度入队时深度加 1空节点也照常入队但在出队时用if (curr_node)跳过因此不需要在入队前判空逻辑更统一由于是逐层推进队内节点的深度单调递增所以max_dept也可以等价为最后一个出队节点的深度但用max维护更直观、更稳健。复杂度时间O(n)空间O(w)w为队列最大宽度平衡二叉树时约为O(n/2)量级。它的最大优势是把递归调用栈换成了堆上的队列在处理深度高达 10000 的单链树时不会爆栈。五、两种思路对比小结维度DFS 递归后序BFS 迭代层序核心思想深度 1 max(左右子树深度)逐层向下记录层号最大值时间复杂度O(n)O(n)空间复杂度最坏 O(n)链式树递归栈O(w)队列宽度最坏约 n/2代码量3~5 行最简洁约 10 行稍长风险点深链可能栈溢出无递归栈风险适用场景面试手写首选、代码量小生产环境 / 深树 / 防止爆栈对于本题节点总数 10000的限制两种写法在力扣环境下都能顺利通过但面试官常会追问如果树很深怎么办此时能答出 BFS 迭代方案会是明显的加分项。六、举一反三从最大深度到同族题目二叉树深度问题是一个小家族仓库的 DFS 分类目录见 13-DFS 目录中还收录了以下几道同族题目解法可以互相迁移1. 最小深度力扣 111——见 111.二叉树的最小深度。注意不能简单把max换成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; }2. 平衡二叉树剑指 Offer 55-II / No39——见 39-剑指offer.md。直接复用深度计算函数每个节点左右子树高度差不超过 1 即为平衡树。暴力写法是先求深度再判断会重复遍历改进写法是从下往上返回高度、发现不平衡立即返回 -1 剪枝int getDepth(TreeNode* node) { if (node nullptr) return 0; int leftDept getDepth(node-left); if (leftDept -1) return -1; int rightDept getDepth(node-right); if (rightDept -1) return -1; if (abs(leftDept - rightDept) 1) return -1; else return 1 max(leftDept, rightDept); } bool IsBalanced_Solution(TreeNode* pRoot) { if (pRoot nullptr) return true; return getDepth(pRoot) ! -1; }3. 最小高度树面试题 04.02——见 面试题04.02.最小高度树。这是深度的逆问题给定升序数组构造高度最小的二叉搜索树利用二分法取中点为根、递归构造左右子树即可每个节点深度贡献 1整棵树高度天然最小。七、本篇小结面试题55-I 力扣 104是二叉树类题目的地基题递归模板1 max(left, right)要能闭着眼睛写出来并讲清楚后序遍历的含义BFS 层序迭代版要会写、知道它能防爆栈作为深树场景的备选方案掌握深度这一基本量后最小深度、平衡二叉树判断等衍生题都可以建立在其上这是面试官最常做的由浅入深追问路线。仓库中同族题目的完整笔记可继续对照阅读104.二叉树的最大深度、111.二叉树的最小深度、剑指 Offer No38 二叉树深度、剑指 Offer No39 平衡二叉树以及 DFS 分类目录 中其余题目。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐剑指Offer No38 二叉树的深度递归DFS与BFS迭代全解法剖析InterviewGuide 刷题笔记剑指Offer No38 二叉树的深度递归DFS与BFS迭代全解法剖析InterviewGuide 刷题笔记 本文是 InterviewGuide 仓库「文档教程知识库面试题55-I. 二叉树的深度DFS 递归与 BFS 迭代两种解法详解InterviewGuide 力扣刷题笔记面试题55 I. 二叉树的深度DFS 递归与 BFS 迭代两种解法详解InterviewGuide 力扣刷题笔记 本文是 InterviewGuide 项文档教程知识库LeetCode 104. 二叉树的最大深度InterviewGuide 精选 DFS 刷题笔记C 递归与 BFS 全解LeetCode 104. 二叉树的最大深度InterviewGuide 精选 DFS 刷题笔记C 递归与 BFS 全解 本篇是 InterviewG教程上一篇如何零配置实现Jazzy文档自动化测试保障API文档一致性的完整方案下一篇librealsense RealSense 深度相机 SDK 部署调优实战手册从首帧到生产级创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考