"这篇笔记主要讨论了如何计算二叉树的最大深度，包括两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）。"
二叉树的最大深度是衡量一棵二叉树从根节点到最远叶子节点的最长路径上所经过的节点数量。在二叉树中，叶子节点是没有子节点的节点。理解这个概念对于解决二叉树相关的问题至关重要，因为深度可以帮助我们了解树的结构和特性。
### 方法1：深度优先搜索（DFS）
深度优先搜索是一种递归策略，适用于解决此类问题。在DFS中，我们首先递归地计算左子树和右子树的最大深度，然后取两者中的较大值加1，作为当前节点的最大深度。当遇到空节点时，返回0表示没有深度。以下是Java实现的DFS算法：
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
```
DFS的时间复杂度是O(n)，其中n是二叉树的节点数，因为每个节点只会被访问一次。空间复杂度是O(height)，高度表示二叉树的高度，因为递归调用会使用栈空间，其深度等于二叉树的高度。
### 方法2：广度优先搜索（BFS）
广度优先搜索通常使用队列数据结构来实现。在BFS中，我们逐层遍历二叉树，每次处理完一层的所有节点后，再将下一层的所有节点放入队列。以下是Python实现的BFS算法：
```python
from collections import deque
class Solution:
def maxDepth(self, root):
if not root:
return 0
queue = deque([(root, 1)])
max_depth = 0
while queue:
node, depth = queue.popleft()
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
max_depth = max(max_depth, depth)
return max_depth
```
BFS的时间复杂度同样是O(n)，因为它也需要访问每个节点一次。空间复杂度是O(w)，w是二叉树的宽度，即最宽的一层的节点数。在最坏情况下，如果二叉树是完全平衡的，w等于2^(h-1)，其中h是高度，所以空间复杂度也是O(height)。
总结来说，对于求解二叉树的最大深度，DFS和BFS都是有效的方法，但它们在时间和空间复杂度上有所不同。在实际应用中，选择哪种方法取决于具体场景和资源限制。
我的内容管理
展开
