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

文章目录LeetCode 104. 二叉树的最大深度 —— BFS / 队列解法前置知识队列常用操作1. 创建队列2. 从队尾加入元素3. 从队首取出元素4. 查看当前队列长度为什么队列可以解决最大深度整体流程第一轮第二轮第三轮为什么要先记录 level_size最终代码这道题最核心的思路DFS 和 BFS 的区别复杂度分析LeetCode 104. 二叉树的最大深度 —— BFS / 队列解法上一篇已经用 DFS 递归解决了这道题。二叉树基础、TreeNode、root的理解以及 DFS 递归思路可以看上一篇 上一个解决方法这一篇换一种方法BFS 队列。会好理解点。前置知识队列队列最重要的特点是先进先出FIFOFirst In First Out可以理解成排队先进入队列的元素 ↓ 先被取出来例如进入顺序1 - 2 - 3 取出顺序1 - 2 - 3Python 中需要使用这个不过leetcode不需要特意引入fromcollectionsimportdeque创建队列qdeque()常用操作1. 创建队列qdeque()如果一开始就要放入根节点qdeque([root])注意这里放进去的是根节点这个 TreeNode 对象并不是把整棵树转换成队列。 为什么是[root]而不是root其实和这种写法效果是一样的qdeque()q.append(root)最终队列中都会保存根节点root。区别在于deque()创建队列时可以传入一个可迭代对象让它根据这个对象初始化队列。但是root本身只是一个TreeNode对象并不是可迭代对象所以不能直接qdeque(root)因此需要用[root]把它包装成一个列表。不过需要注意这里的[root]不是把二叉树转换成列表。也不是复制一个新的节点。它只是创建了一个列表里面保存了root这个TreeNode对象的引用。然后deque()根据这个列表初始化队列。所以表示创建一个队列 ↓ 初始放入一个元素根节点 root后续从队列中取出的仍然是完整的TreeNode对象因此依然可以访问node.left node.right继续遍历它连接的子节点。2. 从队尾加入元素q.append(node)例如q.append(node.left)q.append(node.right)3. 从队首取出元素nodeq.popleft()popleft()会把最早进入队列的元素取出来。也就是最前面或者说最左边的那个。所以叫 popleft这正好符合先进先出4. 查看当前队列长度len(q)在这道题里这一步非常重要因为level_sizelen(q)可以记录当前这一层有多少个节点。为什么队列可以解决最大深度BFS 是广度优先搜索。和 DFS 一条路径一直往下走不同BFS 是一层一层遍历二叉树。例如3 / \ 9 20 / \ 15 7BFS 的遍历过程可以理解成第 1 层3 第 2 层9 20 第 3 层15 7所以这道题有一个很直接的思路遍历了多少层最大深度就是多少。整体流程先判断特殊情况ifrootisNone:return0如果根节点为空说明整棵树都不存在深度就是 0。也就是其中一个测试用例root[]然后qdeque([root])depth0此时队列中只有根节点。第一轮例如q [3]先记录level_sizelen(q)得到level_size 1说明当前这一层只有一个节点。然后for_inrange(level_size):只循环一次。取出nodeq.popleft()得到3然后把它的左右孩子加入队列q [9, 20]这一层处理完depth1所以depth 1第二轮此时q [9, 20]所以level_size2这一层有两个节点需要循环两次。第一次弹出 99 没有左右孩子所以不加入新的节点。此时q [20]第二次弹出 2020 有两个孩子15 7加入队尾q [15, 7]第二层处理完depth 2第三轮此时q [15, 7]两个节点都没有孩子。把它们弹出之后不再加入新的节点。最后q []这一层结束depth 3因为队列已经为空whileq:不再满足循环结束。最终最大深度 3为什么要先记录 level_size这一句level_sizelen(q)非常关键。因为在处理当前这一层时我们会不断把下一层的节点加入队列。例如当前 q [9, 20]处理20时又会加入15, 7如果不提前记录level_size2当前层和下一层就会混在一起。所以level_sizelen(q)相当于先把这一层需要处理几个节点固定下来。最终代码fromcollectionsimportdequeclassSolution:defmaxDepth(self,root:Optional[TreeNode])-int:ifrootisNone:return0qdeque([root])depth0whileq:level_sizelen(q)for_inrange(level_size):nodeq.popleft()# 左孩子ifnode.left:q.append(node.left)# 右孩子ifnode.right:q.append(node.right)depth1returndepth这道题最核心的思路可以简单记成队列中保存当前层的节点 ↓ 记录当前层节点数量 ↓ 依次弹出当前层节点 ↓ 把它们的左右孩子加入队尾 ↓ 当前层处理完成 ↓ depth 1 ↓ 继续下一层这里利用的就是队列先进先出的特点。DFS 和 BFS 的区别上一篇使用的是DFS 递归核心思路先不断往深处走 再把结果一层层返回这一篇使用的是BFS 队列核心思路一层一层遍历 每处理完一层 depth 1所以同一道题可以从两个不同方向理解DFS 当前深度 1 max(左子树深度, 右子树深度) BFS 遍历了多少层 最大深度复杂度分析设二叉树一共有n个节点。每个节点只会进入队列一次、弹出一次。所以时间复杂度O(n)队列中最多可能同时保存某一层的所有节点。所以空间复杂度O(n)最坏情况下某一层可能包含大量节点。