LeetCode104.二叉树的最大深度-深度优先与广度优先策略

题目描述：

给定一棵二叉树，目标是找到这棵树的最大深度。这里的最大深度指的是从根节点到最远的叶子节点之间的最长路径所包含的节点数。例如，对于二叉树 [3,9,20,null,null,15,7]，其结构如下：

3 / \ 9 20 / \ 15 7

该树的最大深度为3。

解决方案一：使用深度优先搜索（DFS）

核心思想在于，如果已知某节点的左子树和右子树的最大深度分别为a和b，那么该节点的最大深度就是max(a, b) + 1。这个过程可以通过递归实现，每次递归调用时都尝试计算当前节点的左子树和右子树的最大深度，直到遇到空节点为止。

Java代码示例：

public class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } }

复杂度分析：

• 时间复杂度：O(n)，因为每个节点都会被访问一次。
• 空间复杂度：O(h)，其中h是树的高度。这是因为递归调用栈的深度等于树的高度。

解决方案二：采用广度优先搜索（BFS）

此方法的核心在于层次遍历整棵树。通过使用队列来管理每一层的节点，逐层处理直到队列为空。每处理完一层，就增加深度计数器的值。

具体步骤包括：

1. 初始化一个队列，并将根节点加入队列。
2. 进入循环，只要队列非空就继续。
3. 对于队列中的每一个节点，将其左右子节点依次加入队列（如果存在的话）。
4. 完成一层的遍历后，增加深度计数器。

Java代码示例：

import java.util.LinkedList; import java.util.Queue; public class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; Queue queue = new LinkedList<>(); queue.add(root); int depth = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i 

复杂度分析：

• 时间复杂度：O(n)，因为每个节点都会被访问一次。
• 空间复杂度：O(n)，在最坏的情况下，队列中可能会包含所有的节点。