• 教程

本篇是 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; queue<pair<TreeNode*, 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% 的提交。

该实现的核心思想是在队列元素中携带深度信息：

• 队列元素类型为pair<TreeNode*, int>，第一个分量是节点指针，第二个分量是该节点所处的深度；
• 根节点以深度 1 入队；
• 每次弹出队首元素，用max_dept = max(max_dept, curr_dept)持续更新已到达的最大深度；
• 无论左右孩子是否为nullptr都直接入队，并在取出节点时用if (curr_node)跳过空节点——这样写的好处是无需在入队前做空指针判断，逻辑更统一，代价是队列中会短暂混入空指针元素（可以推断，对空间占用有轻微增加，但不影响正确性）。

另外，pair的初始化使用了 C++11 的列表初始化语法{root, 1}与{curr_node->left, curr_dept + 1}，这是该题解适用于 C++11 及以上标准的细节；queue与pair分别来自标准库头文件<queue>与<utility>，在力扣的评测环境中默认包含。

空间复杂度对比：递归 vs 迭代

可以看到，二者在时间上都无法优于 O(n)（必须遍历全部节点），差别主要体现在空间分配的位置：DFS 吃的是系统调用栈，BFS 吃的是堆上动态分配的队列。对于节点总数上限高达 10000 的题目（见仓库中 面试题55-I.二叉树的深度 的提示），递归一般不会出问题；但如果在生产环境或内存受限场景处理超大/极不平衡的树，BFS 或显式栈的迭代写法是更稳妥的选择。

同源题目联动：仓库中的延伸训练

「最大深度」绝不是孤立的一道题，仓库的 DFS 分类下还沉淀了一系列同源题，建议按如下顺序串联练习，一通百通：

1. 面试题55-I.二叉树的深度：与本题完全相同的剑指 Offer 原题（节点总数 <= 10000），可以把它当作 104 题的"换皮复现"，用于检验自己是否真的掌握了递归写法——该文档给出的解法与本题解法一一致，提交数据记录为 4 ms、击败 99.36% 的 C++ 提交。

2. 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 放在一起对比，能一次性厘清"最大/最小深度"两种递推的边界条件。

3. 面试题04.02.最小高度树：将"树的深度"知识点反向应用——给定升序数组构造高度最小的二叉搜索树（BST）。利用"取中间元素为根、左右区间递归建树"的 DFS 分治策略，天然得到平衡树，从而保证高度最小：

class Solution { private: TreeNode* dfs(vector<int>& 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(vector<int>& 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。把这句话的递归形态与迭代形态都写熟练，"树的深度"这一族题目（最大深度、最小深度、最小高度树、判断平衡树）就都能从容应对了。

• 教程