104. 二叉树的最大深度

104. 二叉树的最大深度

简单

给定一个二叉树root，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：3

示例 2：

输入：root = [1,null,2] 输出：2

提示：

• 树中节点的数量在[0, 104]区间内。
• -100 <= Node.val <= 100

📝 核心笔记：二叉树的最大深度 (Maximum Depth of Binary Tree)

1. 核心思想 (一句话总结)

“向左右下属汇报工作：我的高度 = max(左下属高度, 右下属高度) + 1 (我这一层)。”

这是一个典型的后序遍历 (Post-order Traversal)模型：

1. 先求左子树的深度。
2. 再求右子树的深度。
3. 最后结合两者，算出自己的深度。

2. 算法流程 (递归三步曲)

1. 终止条件 (Base Case)：

• • 如果root == null，说明到了空节点（叶子节点的下一层），深度为0。

1. 递推 (Recurse)：

• • int l = maxDepth(root.left)
  • int r = maxDepth(root.right)

1. 回归 (Return)：

• • 返回Math.max(l, r) + 1。这个+1代表当前节点本身贡献的一层高度。

🔍 代码回忆清单

// 题目：LC 104. Maximum Depth of Binary Tree class Solution { public int maxDepth(TreeNode root) { // 1. 递归终止条件：越过叶子节点，高度归零 if (root == null) { return 0; } // 2. 问左孩子有多高 int lDepth = maxDepth(root.left); // 3. 问右孩子有多高 int rDepth = maxDepth(root.right); // 4. 选高的那个，加上自己这一层，汇报给上级 return Math.max(lDepth, rDepth) + 1; } }

⚡ 快速复习 CheckList (易错点 & 扩展)

• [ ]DFS vs BFS？

• • DFS (本解法)：代码短，$O(H)$ 空间（栈深度）。
  • BFS (层序遍历)：使用Queue。每遍历完一层，depth++。虽然代码长一点，但思路也很直观。如果面试官问“不用递归怎么做”，就写 BFS。

• [ ]时间复杂度？

• • 因为每个节点都必须被访问一次才能确定最大深度。

• [ ]空间复杂度？

• • 。平均情况 $O(\log N)$，最坏情况（退化成链表） $O(N)$。

🖼️ 数字演练

树结构：

3 / \ 9 20 / \ 15 7

1. maxDepth(9): 左null(0), 右null(0) ->max(0,0)+1=1。
2. maxDepth(15):max(0,0)+1=1。
3. maxDepth(7):max(0,0)+1=1。
4. maxDepth(20): 左(15返回1), 右(7返回1) ->max(1,1)+1=2。
5. maxDepth(3): 左(9返回1), 右(20返回2) ->max(1,2)+1=3。

结果：3。