怎么求出python二叉树的最大深度

# 怎么求出Python二叉树的最大深度

## 目录
1. [二叉树基础概念](#二叉树基础概念)
2. [最大深度的定义](#最大深度的定义)
3. [递归解法](#递归解法)
4. [迭代解法（BFS）](#迭代解法bfs)
5. [复杂度分析](#复杂度分析)
6. [完整代码示例](#完整代码示例)
7. [应用场景](#应用场景)
8. [总结](#总结)

---

## 二叉树基础概念
二叉树（Binary Tree）是每个节点最多有两个子节点的树结构，通常称为：
- 左子节点（left child）
- 右子节点（right child）

基本结构示例：
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

最大深度的定义

最大深度是指从根节点到最远叶子节点的最长路径上的节点数。例如：

    3
   / \
  9  20
    /  \
   15   7

最大深度为3（路径3→20→7或3→20→15）。

递归解法

核心思想

• 二叉树的最大深度 = 1 + max(左子树深度, 右子树深度)
• 基线条件：空节点深度为0

代码实现

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

执行过程分析

以示例树为例： 1. 根节点3 → 计算max(左子树9, 右子树20) 2. 节点9 → 左右均为空 → 返回1 3. 节点20 → max(左15, 右7) 4. 节点15和7 → 均返回1 5. 最终结果：1 + max(1, 2) = 3

迭代解法（BFS）

广度优先搜索思路

• 使用队列按层遍历
• 每处理完一层，深度+1

代码实现

from collections import deque

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    
    queue = deque([root])
    depth = 0
    
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

执行示例

队列变化：
[3] → depth=1
[9,20] → depth=2
[15,7] → depth=3
[] → 结束

复杂度分析

• h为树高度，w为树最大宽度（最宽层的节点数）

完整代码示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 递归解法
def maxDepth_recursive(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth_recursive(root.left), maxDepth_recursive(root.right))

# BFS解法
from collections import deque

def maxDepth_bfs(root: TreeNode) -> int:
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

# 测试用例
if __name__ == "__main__":
    # 构建示例树
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    
    print(f"递归解法结果: {maxDepth_recursive(root)}")  # 输出3
    print(f"BFS解法结果: {maxDepth_bfs(root)}")       # 输出3

应用场景

1. 平衡性检查：判断AVL树是否需要旋转
2. 文件系统：计算目录树的最大嵌套深度
3. 游戏：评估决策树的最远可能路径
4. 网络路由：确定最优路径跳数

总结

• 递归法代码简洁，适合理解树结构
• BFS法更适合宽而浅的树结构
• 实际选择时需考虑：
  • 树的高度（递归栈深度）
  • 是否需要层序遍历的其他信息

掌握这两种方法能解决LeetCode 104题及其他衍生问题（如最小深度、直径等）。 “`

注：实际字符数约1300字（含代码和格式标记）。如需调整内容细节，可进一步扩展算法原理或增加可视化示例。