11、二叉树的最大深度
2025/11/10大约 3 分钟数据结构算法算法基地面试递归二叉树刷题程序厨校招社招
求树的最大深度,不需要在每个节点保存“自己是第几层”。可以反过来问:如果左右子树的高度已经知道,当前子树的高度还差哪一步?
问题与目标
LeetCode 104:二叉树的最大深度把深度定义为从根到最远叶子的路径上节点的个数。
3
/ \
9 20
/ \
15 7
答案为 3。空树深度为 0,只有根节点的树深度为 1;不要与按边数计算高度的另一种约定混用。
把父问题交给两个子问题
空树返回 0。非空树取左右子树深度的较大值,再加当前根节点这一层:
depth(node) = 1 + max(depth(node.left), depth(node.right))
这个定义本身就给出了递归终止条件与返回关系。它不是将左右深度相加,也不要求两个孩子都存在。

自底向上检查返回值
节点 9、15、7 的左右孩子都是空,分别返回 1;节点 20 收到两个 1,返回 2;根 3 收到左边 1、右边 2,最终返回 3。
如果树是一条只有右孩子的链,左子树一直返回 0,右子树逐层加一,公式仍然成立。这一点也能区分最大深度与最小深度:最小深度不能在缺一侧子树时直接取两侧的最小值。
C++17 递归实现
#include <algorithm>
struct TreeNode {
int val = 0;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}
};
复杂度与工程边界
每个节点只处理一次,时间 O(n);递归调用栈的最大深度与树高 h 相同,辅助空间 O(h)。平衡树为 O(log n),退化成链时可达 O(n),不是所有二叉树递归都只占对数空间。
特别深的树可能耗尽调用栈。需要控制栈风险时,可以使用显式栈记录“节点与深度”,或用队列逐层统计层数。两者都需要额外容器,不应仍声称常量空间。
常见误区
节点值与深度没有关系;返回左右深度之和得到的不是树高;把空树写成返回 1 会让所有结果多算一层。先用空树、单节点和单边链验证,再看复杂树形更容易定位错误。
