104. 二叉树的最大深度#

生命的高度：理解树的深度#

想象一棵树，它从地底向天空生长。树的深度不仅仅是枝干的长度，更是生命的垂直延伸。在二叉树的世界里，深度代表了从根节点到最远叶子节点的最长路径。这是一种从根本到极限的探索旅程。

问题描述#

题目目标#

给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1#

输入： root = [3,9,20,null,null,15,7] 输出： 3 二叉树示意：

text

说明： 从根节点到最深叶子节点一共有 3 层，因此最大深度是 3。

补充说明#

二叉树通常使用层序数组表示，null 表示该位置没有节点。

深度的本质：递归的诗与逻辑#

二叉树的最大深度（LeetCode第104题）本质上是一个递归问题，它蕴含着令人惊叹的优雅逻辑。想象你正站在树的根部，要测量这棵树能长到多高。你会怎么做？很自然地，你会先测量左子树的高度，再测量右子树的高度，然后选择一个更高的，再加上根节点本身的高度。

递归思考的魔力#

递归解法的核心在于将复杂问题分解为相似的小问题：

如果是空树，深度为0
如果是叶子节点，深度为1
对于非叶子节点，深度 = max(左子树深度, 右子树深度) + 1

这种思路就像是一个不断缩小规模的放大镜，每一次递归都让我们更接近最终答案。

代码实现：从思路到现实#

public int maxDepth(TreeNode root) {
    // 递归终止条件：空节点的深度定义为 0
    if (root == null) return 0;

    // 递归计算左子树深度
    int leftDepth = maxDepth(root.left);
    // 递归计算右子树深度
    int rightDepth = maxDepth(root.right);

    // 当前节点深度 = 左右子树较大深度 + 当前节点这一层（+1）
    return Math.max(leftDepth, rightDepth) + 1;
}

java

代码解析：每一行的思考#

if (root == null) return 0;
- 这是递归的”安全阀”，处理空树或遍历到叶子节点的情况
- 确保递归不会无限进行
int leftDepth = maxDepth(root.left);
- 递归计算左子树深度
- 这一行体现了”分治”的智慧，将大问题拆分为相似的小问题
int rightDepth = maxDepth(root.right);
- 同理计算右子树深度
- 左右子树的深度互相独立，可以并行思考
return Math.max(leftDepth, rightDepth) + 1;
- 选择更深的子树，并加上当前节点的高度
- “+1”是关键，代表当前节点对总深度的贡献

深度分析：性能与复杂度#

时间复杂度：O(n)#

每个节点只访问一次
n为树中节点总数
我们像一个勤奋的测量员，脚踏实地地丈量每一个节点

空间复杂度：O(h)#

h为树的高度
空间消耗来自递归调用栈
最坏情况（完全不平衡的树）可达O(n)
最好情况（完全平衡的树）为O(log n)

迭代方法：另一种视角#

递归优雅，但有时我们需要更显式的控制。以下是迭代版本：

public int maxDepth(TreeNode root) {
    // 边界情况：空树深度为 0
    if (root == null) return 0;

    // 队列用于层序遍历，按层从上到下访问节点
    Queue<TreeNode> queue = new LinkedList<>();
    // 根节点先入队，作为第 1 层起点
    queue.offer(root);

    // depth 记录已经完整遍历过的层数
    int depth = 0;
    // 队列不为空表示还有下一层节点待处理
    while (!queue.isEmpty()) {
        // 先固定当前层节点数量，避免与下一层混在一起
        int size = queue.size();

        // 逐个处理当前层的节点
        for (int i = 0; i < size; i++) {
            // 取出当前层的一个节点
            TreeNode node = queue.poll();

            // 左子节点存在则入队，留给下一层处理
            if (node.left != null) queue.offer(node.left);
            // 右子节点存在则入队，留给下一层处理
            if (node.right != null) queue.offer(node.right);
        }

        // 当前层处理结束，树深度加 1
        depth++;
    }

    // 返回总层数，即最大深度
    return depth;
}

java

思考与延伸#

如何处理不同类型的二叉树？
深度与平衡性有何关联？
还有哪些递归可以如此优雅地解决？

实际应用场景#

文件系统目录深度
组织架构层级分析
网络拓扑结构分析
博弈算法中的搜索深度控制

启示：递归的智慧#

二叉树最大深度不仅仅是一道算法题，更是递归思想的生动诠释。它教会我们：

将复杂问题分解为相似的小问题
信任递归的”magic”：小问题的解会汇聚成大问题的答案
代码的优雅往往来自思维的清晰

探索二叉树就像攀登一座知识的高峰，重要的是保持好奇，步步为营！