hot100 二叉树的最大深度(104)
本题采用分治递归算法（又称“自底向上深度优先搜索法”）解决二叉树的最大深度计算问题。其核心本质是将全局树高问题拆解为左右子树的局部子问题，利用递归回溯的特性，在叶子节点向根节点回溯的过程中实现深度的累加与最值筛选。当前提供的源码实现了在时间复杂度O(n)和额外空间复杂度O(height)条件下的全局最优树结构检索。
一、 问题本质与数据模型
对于一个给定的二叉树，题目要求的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
二叉树本身具有天然的递归拓扑结构：每一个非空节点都可以作为一棵独立子树的根节点。因此，求解整棵树的最大深度可以完全等价地转化为一个自底向上的递推模型：
任何一个节点处的最大深度 = max(左子树的最大深度, 右子树的最大深度) + 1
为了破除递归的无限循环，算法引入了“空节点基准退出模型”。当程序深度探测至叶子节点的两侧空指针（null）时，该位置在几何空间上不占据任何高度，表现出基础的边界属性：
命中空节点：返回深度 0。
回溯父节点：将子树反馈的高度加 1，作为当前节点的贡献高度。
这种自底向上的高度吞吐机制，赋予了递归栈类似于“弹簧测力计”的物理特性，每次弹回都能产生准确的局部深度数据。
二、 算法演进对比
在解决二叉树深度检索的问题时，递归分治法在代码优雅度与时空资源的平衡上达到了经典的状态：
| 解法名称 | 时间复杂度 | 空间复杂度 | 核心原理 | 物理瓶颈 / 缺陷 |
| 层序遍历法（BFS 迭代） | O(n) | O(n) | 利用队列进行按层扫描，每扫描完一层，深度计数器加 1 | 需要显式借助队列存储当前层的所有节点，在完全二叉树下其最底层宽度可达 n/2，内存开销较大 |
| 自顶向下深搜（DFS 携带全局变量） | O(n) | O(height) | 从根节点出发向下传递当前深度，并在叶子节点处更新全局最大值 | 需要维护外部全局变量，且代码逻辑相对冗余，不符合纯粹的分治思想 |
| 分治递归法（当前解法） | O(n) | O(height) | 利用左右子树高度的确定性，自底向上严格收敛，代码极度精简 | 极度倾斜的树（如链表状二叉树）会导致递归栈深度退化为 O(n) |
三、 核心分支控制逻辑与决策证明
当前源码的控制流完全依赖于函数入口的边界防护以及自底向上的数据归纳，其内部决策分支证明如下：
1. 基准出口分支：if (root == null)
执行：直接返回0。
物理意义：当前坐标已越过叶子节点，到达不存在的空子树，检索流程在该分支触底并启动回溯。
2. 局部探底分支：int lRes = maxDepth(root.left);与int rRes = maxDepth(root.right);
执行：分别向左、右子节点派发相同的求解任务。
数学证明：基于数学归纳法，假设当前节点的左右子树已经正确计算出了它们各自的最大深度分别为
lRes和rRes。
3. 深度归纳合并：return Math.max(lRes, rRes) + 1;
执行：取左右子树深度较大者，加1后返回给上一层。
数学证明：从当前节点出发向下的最长路径，必然通过它“更高的一侧”子树。因此，当前子树的整体高度等于高子树的高度加上当前节点自身所占的一层物理高度（即
+ 1）。结论：该返回值完美契合二叉树深度的递归定义，确保了数据向上推导的精准性。
四、 算法执行状态机步进示例
以输入二叉树root = [3, 9, 20, null, null, 15, 7]（规模 5 个有效节点）为例，递归调用栈的状态机演进及回溯过程如下表所示：
| 步骤 | 当前处理节点 | 触发的分支动作 | 接收到的子节点返回值 | 执行的核心合并决策 | 局部栈反馈高度说明 |
| 1 | 节点 9 | 探测左右子节点 | 左=null (0), 右=null (0) | Math.max(0, 0) + 1 | 节点 9 处的局部高度为1，向上传递 |
| 2 | 节点 15 | 探测左右子节点 | 左=null (0), 右=null (0) | Math.max(0, 0) + 1 | 节点 15 处的局部高度为1，向上传递 |
| 3 | 节点 7 | 探测左右子节点 | 左=null (0), 右=null (0) | Math.max(0, 0) + 1 | 节点 7 处的局部高度为1，向上传递 |
| 4 | 节点 20 | 接收 15 和 7 的反馈 | 左=15 (1), 右=7 (1) | Math.max(1, 1) + 1 | 节点 20 处的局部高度为2，向上传递 |
| 5 | 节点 3 (根) | 接收 9 和 20 的反馈 | 左=9 (1), 右=20 (2) | Math.max(1, 2) + 1 | 全局高度锁定为3，程序最终返回 |
五、 源码实现
class Solution { public int maxDepth(TreeNode root) { // 边界安全检查：若当前节点为空，说明已越过叶子节点，高度贡献为 0 if (root == null) { return 0; } // 递归获取左子树的最大深度 int lRes = maxDepth(root.left); // 递归获取右子树的最大深度 int rRes = maxDepth(root.right); // 核心决策：当前节点的最大深度等于左右子树中较大深度加 1（当前节点自身高度） return Math.max(lRes, rRes) + 1; } }六、 复杂度分析
1. 时间复杂度：O(n)
分析：算法采用标准的深度优先遍历模式。在递归执行过程中，二叉树中的每一个节点
TreeNode都会且仅会被访问一次（进栈一次，出栈一次）。结论：总的操作次数与二叉树的节点总数
n呈严格的线性正比关系，即时间复杂度为O(n)。
2. 空间复杂度：O(height)
分析：该算法没有申请任何额外的外部数据结构，其空间消耗完全取决于递归调用时系统开辟的函数隐式栈深度。隐式栈的最大深度等于二叉树的最大高度
height。在最坏情况下（二叉树退化为单链表结构），树高
height等于n，空间复杂度退化为O(n)。在最好情况下（二叉树为完全二叉树或平衡二叉树），树高
height严格等于log n，空间复杂度为O(log n)。
结论：内存空间消耗在通用状态下定义为常数阶基础上的拓扑层级消耗，即O(height)。