CodeBrick 博客

Appearance

二叉树的最大深度：一遍递归即满分 ​

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。二叉树最大深度是「树与二叉树」这一章最基础的一道后序遍历应用题，和 2014·41 二叉树 WPL 是同一族——一趟遍历带着状态往上传。它是经典训练题，不是真题，也不押题。

题目 ​

给定一棵二叉树的根结点，求它的最大深度——从根结点到最远叶结点的最长路径上的结点数。空树的最大深度为 0，只有根结点的树最大深度为 1。

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把递归的边界和顺序写准上。

直观解法：一遍递归 ​

一棵树的最大深度，等于「左子树的最大深度」和「右子树的最大深度」中较大的那个，再加上根结点自己这一层。这是一个天然的递归定义：子问题（左右子树的深度）算完之后，用它们组合出当前结点的答案——这正是后序遍历的顺序（先处理左右子树，再处理根）。

c
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int maxDepth(TreeNode *root) {
    if (root == NULL) return 0;                      // 空树深度为 0
    int leftDepth  = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;   // 较大者加一
}

拿一棵简单的树走一遍：根 1，左孩子 2，2 又有左孩子 4；根 1 还有右孩子 3。递归到 4 时左右孩子都是 NULL，maxDepth(4) 返回 1；结点 2 的左深度是 1（来自 4）、右深度是 0（没有右孩子），取较大值 1 再加一，maxDepth(2) 返回 2；结点 3 没有孩子，maxDepth(3) 返回 1；根结点左深度 2（来自结点 2）、右深度 1（来自结点 3），取较大值 2 再加一，最终返回 3。

复杂度：每个结点恰好被访问一次、做常数次比较，时间 O(n)；递归栈深度等于树高，空间 O(h)（h 为树高，最坏 O(n)）。

为什么它就是满分解 ​

用总纲的「找浪费三问」审一遍，三问全部答「没有」：

  1. 有没有重复扫描？ 没有。每个结点只在自己所在的那次递归调用里被访问一次，不会因为求别的结点的深度而被重复访问。
  2. 有没有重算已知的东西？ 没有。左右子树的深度各自只算一次，算完立刻用来组合出当前结点的答案，不存在同一棵子树的深度被外层多次重新计算的情况。
  3. 有没有放着性质不用？ 没有。题目要的「子树深度」正好靠递归的返回值自然向上传递,不需要额外的数据结构去记录。

更根本的一条：要确定最大深度，至少要知道树上每个结点是否存在（否则漏看的那个结点如果恰好在最深的那条路径上，答案就错了）——访问一遍所有结点就是 O(n) 的下界，任何正确算法都躲不开。碰到下界，就没有优化空间，直观写法即最优。

真正的难点在边界和顺序 ​

分不在优化上,在三处容易翻车的地方：

  • 空树的深度是 0，不是 -1、也不是异常。递归的终止条件 root == NULL 返回 0，是整个递归能正确工作的地基——如果这个基准返回值错了，往上传递的每一层结果都会跟着错位。
  • 「加一」必须在两个子问题的结果都拿到之后。先递归求出 leftDepth 和 rightDepth，再用它们的较大值加一得到当前结点的深度——这个顺序正是后序遍历「先子树、后根」的体现。如果在递归调用之前就想着加一，会让代码逻辑和递归定义脱节，容易写错。
  • 只有一个叶结点时，深度算的是 1，不是 0。叶结点的左右孩子都是 NULL，两次递归调用都返回 0，取较大值 0 再加一得到 1——手算一棵只有根结点的树，是验证边界写对没有的最快方法。

一遍递归,看一遍 ​

用一棵简单的树（根 1，左孩子 2 挂着左孩子 4，右孩子 3）演示后序遍历式的深度计算——先递归到最深的叶结点算出 0，逐层往上取较大值加一：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足 ​

这道题结构简单,过度设计的空间不大,但有两个常见的「想复杂了」：

  • 想额外维护一个全局最大值变量,自顶向下传递当前深度。这种写法（dfs(node, depth)，每到一个结点就用 depth 更新全局最大值）确实也能算对，复杂度也是 O(n)，但它引入了额外的全局状态和参数传递，而后序遍历「返回值自底向上组合」的写法不需要任何额外状态，更短也更不容易出错——两种写法效率相当，选更简洁的那种。
  • 想用层序遍历（BFS）数层数。层序遍历确实也能求出最大深度（数一共扫了几层），但需要额外维护一个队列，代码量比递归大不少,对这道题而言没有必要。

下一步 ​

相关真题（6题）

2025Q3选择题2分
去刷题

二叉树顺序存储：下标从 0 开始时，根据 2i+1/2i+2 规则判断哪个数组不构成合法二叉树

二叉树基础（性质+存储）
2020Q3选择题2分
去刷题

二叉树顺序存储：高度为 5 的任意树最多需要 31 个存储单元

二叉树基础（性质+存储）
2018Q4选择题2分
去刷题

满二叉树性质：结点总数与叶结点数的关系 2k-1

二叉树基础（性质+存储）
2015Q2选择题2分
去刷题

卡特兰数：先序序列为 a,b,c,d 的不同二叉树个数为 C(2n,n)/(n+1)=14

二叉树基础（性质+存储）
2011Q4选择题2分
去刷题

完全二叉树：根据总结点数计算叶结点个数

二叉树基础（性质+存储）
2009Q5选择题2分
去刷题

完全二叉树：第 6 层有 8 个叶结点时最多 111 个结点

二叉树基础（性质+存储）