DAY3：LeetCode 104. 二叉树的最大深度（另一个方法）

文章目录

• LeetCode 104. 二叉树的最大深度 —— BFS / 队列解法
• 前置知识：队列
• • 常用操作
  • • 1. 创建队列
    • 2. 从队尾加入元素
    • 3. 从队首取出元素
    • 4. 查看当前队列长度
• 为什么队列可以解决最大深度？
• 整体流程
• • 第一轮
  • 第二轮
  • 第三轮
• 为什么要先记录 level_size？
• 最终代码
• 这道题最核心的思路
• DFS 和 BFS 的区别
• 复杂度分析

LeetCode 104. 二叉树的最大深度 —— BFS / 队列解法

上一篇已经用 DFS + 递归解决了这道题。

二叉树基础、TreeNode、root 的理解，以及 DFS 递归思路，可以看上一篇： 上一个解决方法

这一篇换一种方法：BFS + 队列。会好理解点。

前置知识：队列

队列最重要的特点是：

先进先出（FIFO，First In First Out）

可以理解成排队：

先进入队列的元素
↓
先被取出来

例如：

进入顺序：
1 -> 2 -> 3

取出顺序：
1 -> 2 -> 3

Python 中可以使用：

from collections import deque

创建队列：

q = deque()

常用操作

1. 创建队列

q = deque()

如果一开始就要放入根节点：

q = deque([root])

注意，这里放进去的是 根节点这个 TreeNode 对象，不是把整棵树转换成队列。

2. 从队尾加入元素

q.append(node)

例如：

q.append(node.left)
q.append(node.right)

3. 从队首取出元素

node = q.popleft()

popleft() 会把最早进入队列的元素取出来。

这正好符合：

先进先出

4. 查看当前队列长度

len(q)

在这道题里，这一步非常重要，因为：

level_size = len(q)

可以记录 当前这一层有多少个节点。

为什么队列可以解决最大深度？

BFS 是广度优先搜索。

和 DFS 一条路径一直往下走不同，BFS 是：

一层一层遍历二叉树。

例如：

3
/ \\
9 20
/ \\
15 7

BFS 的遍历过程可以理解成：

第 1 层：
3

第 2 层：
9 20

第 3 层：
15 7

所以这道题有一个很直接的思路：

遍历了多少层，最大深度就是多少。

整体流程

先判断特殊情况：

if root is None:
return 0

如果根节点为空，说明整棵树都不存在，深度就是 0。

也就是其中一个测试用例：

root = []

然后：

q = deque([root])
depth = 0

此时队列中只有根节点。

第一轮

例如：

q = [3]

先记录：

level_size = len(q)

得到：

level_size = 1

说明当前这一层只有一个节点。

然后：

for _ in range(level_size):

只循环一次。

取出：

node = q.popleft()

得到：

3

然后把它的左右孩子加入队列：

q = [9, 20]

这一层处理完：

depth += 1

所以：

depth = 1

第二轮

此时：

q = [9, 20]

所以：

level_size = 2

这一层有两个节点，需要循环两次。

第一次：

弹出 9

9 没有左右孩子，所以不加入新的节点。

此时：

q = [20]

第二次：

弹出 20

20 有两个孩子：

15
7

加入队尾：

q = [15, 7]

第二层处理完：

depth = 2

第三轮

此时：

q = [15, 7]

两个节点都没有孩子。

把它们弹出之后，不再加入新的节点。

最后：

q = []

这一层结束：

depth = 3

因为队列已经为空：

while q:

不再满足，循环结束。

最终：

最大深度 = 3

为什么要先记录 level_size？

这一句：

level_size = len(q)

非常关键。

因为在处理当前这一层时，我们会不断把下一层的节点加入队列。

例如：

当前：
q = [9, 20]

处理 20 时，又会加入：

15, 7

如果不提前记录：

level_size = 2

当前层和下一层就会混在一起。

所以：

level_size = len(q)

相当于先把：

这一层需要处理几个节点

固定下来。

最终代码

from collections import deque

class Solution:
def maxDepth(self, root: Optional[TreeNode]) –> int:

if root is None:
return 0

q = deque([root])
depth = 0

while q:
level_size = len(q)

for _ in range(level_size):
node = q.popleft()

# 左孩子
if node.left:
q.append(node.left)
# 右孩子
if node.right:
q.append(node.right)

depth += 1

return depth

这道题最核心的思路

可以简单记成：

队列中保存当前层的节点
↓
记录当前层节点数量
↓
依次弹出当前层节点
↓
把它们的左右孩子加入队尾
↓
当前层处理完成
↓
depth + 1
↓
继续下一层

这里利用的就是队列：

先进先出

的特点。

DFS 和 BFS 的区别

上一篇使用的是：

DFS + 递归

核心思路：

先不断往深处走
再把结果一层层返回

这一篇使用的是：

BFS + 队列

核心思路：

一层一层遍历
每处理完一层
depth + 1

所以同一道题可以从两个不同方向理解：

DFS：
当前深度
= 1 + max(左子树深度, 右子树深度)

BFS：
遍历了多少层
= 最大深度

复杂度分析

设二叉树一共有 n 个节点。

每个节点只会进入队列一次、弹出一次。

所以：

• 时间复杂度：O(n)

队列中最多可能同时保存某一层的所有节点。

所以：

• 空间复杂度：O(n)

最坏情况下，某一层可能包含大量节点。