leetcode104：二叉树的最大深度

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

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

示例 1：

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

示例 2：

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

提示：

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

步骤 1：问题分析

• 题目要求：求出二叉树的最大深度，即从根节点到最远叶子节点的最长路径上的节点数。
• 输入输出条件：
  • 输入：根节点root，是一个二叉树的根节点。
  • 输出：树的最大深度（整数）。
• 限制条件：
  • 树中节点数量在 [0, 10^4] 范围内，节点值在 [-100, 100] 范围内。
  • 树可能为空（root为null）。
• 边界条件：
  • 若root为空，则树的深度为0。
  • 若只有一个节点，深度为1。

步骤 2：解题思路

思路分析

计算二叉树的最大深度可以采用递归深度优先搜索（DFS）或广度优先搜索（BFS），在此问题中，我们可以优先考虑递归DFS来简洁地解决。

• DFS递归法：对于每个节点，递归计算其左子树和右子树的深度，最大深度为左右子树深度的最大值加1。
• BFS迭代法：使用队列，从根节点开始，每一层的节点进入队列，直到队列为空。计数遍历的层数即为最大深度。

复杂度分析

• 时间复杂度：O(N)，其中N为二叉树节点的个数，因为每个节点在DFS或BFS中都需要被访问一次。
• 空间复杂度：O(H)，其中H为树的高度。最坏情况下（树为链表），空间复杂度为O(N)，平衡二叉树则为O(log N)。

推荐算法

使用递归DFS法是较优的选择，代码简洁且逻辑清晰。我们递归访问每个节点，并返回其左右子树深度中的较大值加一。

步骤 3：详细代码实现（C++）

步骤 4：算法启发和优化

通过本题可以了解到以下启发：

1. 递归思想的简洁性：递归法非常适合树形结构问题，代码更简洁。
2. 空间优化：在栈消耗过多时，递归方法可以改为BFS以减少深度过大时的栈空间消耗。
3. 面向大规模数据的优化：当数据规模变大时，采用非递归迭代法会更节省内存资源。

步骤 5：实际应用场景

该算法可以广泛应用于计算树结构的深度，在许多实际场景中有重要应用：

• 文件目录系统：计算文件夹的最大嵌套层次，以便确定文件组织的深度。

  • 实现方法：使用递归或队列遍历文件夹树，计算目录的最大深度。

• 组织架构分析：计算公司组织架构的最大层级，帮助分析管理层级深度。

  • 实现方法：使用员工节点构建组织树，通过DFS或BFS计算最大管理层级。

• 编译器解析：计算语法树的最大深度，帮助理解表达式的复杂性。

  • 实现方法：解析语法树的结构，并递归计算语法树节点深度。