题目

思路

一句话：让左右子树各自汇报深度，当前节点的深度就是 1 + max(左子树深度, 右子树深度)。

先想最直白的：从根出发，把所有“根到叶子”的路径都走一遍，每条路径记录经过的节点数，最后取最大值。这个做法当然正确，但需要显式维护当前路径长度和回溯，代码比较绕。

再想按层数：用队列一层一层往下扫，每扫完一整层就把层数加 1，最后扫到第几层就是最大深度。这个想法也很直观，但需要额外处理“这一层在哪里结束、下一层从哪里开始”。

关键观察：树的最大深度有递归结构。以任意节点 u 为根的子树，它的最深路径只有两种走法——要么先进入左子树，要么先进入右子树；无论走哪边，剩下的问题都是同一个“求某棵子树的最大深度”。于是有：

• 空节点的深度是 0，因为没有节点。
• 非空节点的深度是 1 + max(左子树最大深度, 右子树最大深度)，其中 1 是当前节点自己。

递归 DFS 把这个式子直接翻译出来，代码最短，选它做主解法；迭代 DFS 和 BFS 是同一定义下的另外两种实现，放在「扩展三」对照。

解法

1. 若 root 为空，返回 0。
2. 递归求左子树最大深度 left。
3. 递归求右子树最大深度 right。
4. 返回 1 + max(left, right)。

用自造示例从叶子往根走一遍：

根节点 7 汇总出 3，就是整棵树的最大深度。

下图把上面 4 个步骤串成流程，并逐步演示：

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
 int maxDepth(TreeNode* root) {
 if (root == nullptr) re
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。