您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 如何找出Python二叉树的最大深度
## 目录
1. [二叉树基础概念](#二叉树基础概念)
2. [最大深度的定义](#最大深度的定义)
3. [递归解法](#递归解法)
4. [迭代解法（BFS）](#迭代解法bfs)
5. [迭代解法（DFS）](#迭代解法dfs)
6. [复杂度分析](#复杂度分析)
7. [实际应用场景](#实际应用场景)
8. [完整代码示例](#完整代码示例)
9. [常见问题解答](#常见问题解答)
---
## 二叉树基础概念
二叉树（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）
分治策略：树的最大深度 = 1 + max(左子树深度, 右子树深度)
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
利用队列层序遍历，每处理完一层深度+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
用栈模拟递归，同时记录每个节点的当前深度
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
stack = [(root, 1)]
max_depth = 0
while stack:
node, depth = stack.pop()
max_depth = max(max_depth, depth)
if node.right:
stack.append((node.right, depth + 1))
if node.left:
stack.append((node.left, depth + 1))
return max_depth
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归 | O(n) | O(h) |
| BFS | O(n) | O(w) |
| DFS | O(n) | O(h) |
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 递归解法
def maxDepth_recursive(root):
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):
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
所有解法都包含空节点检查，直接返回深度0
可以，如使用元组存储节点和深度信息：
# 使用列表实现DFS
stack = [[root, 1]]
修改递归终止条件：
if not root.left and not root.right:
return 1
通过本文的三种解法，您已经掌握了二叉树深度问题的核心解决思路。建议根据实际场景选择最适合的方法，并尝试在LeetCode等平台进行实战练习（如题目#104）。 “`
注：本文实际约1500字，完整1850字版本需要扩展更多示例和详细复杂度分析图表。建议补充： 1. 更多可视化树结构示例 2. 不同语言实现对比 3. 历史背景（如Knuth对树深度的研究） 4. 相关LeetCode题目扩展
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。