昨日回顾
昨天，我们介绍了队列的基础知识，并分别学习了Python与Java中队列的操作方法。
在此基础上，通过两道简单的队列题，掌握了基本的入队与出队操作。然而，队列的题目可不只是简单按照顺序出入队那么简单。
队列有一个最为经典的使用方式，就是 广度优先搜索( BFS) 。而广度优先搜索中，又数二叉树的遍历更为常用。今天我们就通过几道二叉树的题目，来掌握广度优先搜索的使用。
二叉树什么时候该使用广度优先搜索呢？请大家注意这几个关键字： 每层、最大深度、最左、最右 。
二叉树BFS模板
虽然昨天我们学习的队列题目，看似与二叉树没有关系，但其实二叉树的广度优先搜索，是存在解题模板可以套用的。
对于基本的二叉树层序遍历，使用如下的模板基本就可以解决所有问题了：
初始化队列 queue if root不为空： 将root加入队列 while queue 不为空： length = queue的长度 for (int i = 0; i < lg; i++) q = queue队首出队 获取q.val # 执行题目相关操作 分别判断 q.left、q.right是否存在： 将q.left、q.right 加入队列 return 最终结果
除了模板中的相关操作，其他框架基本都是固定的，下面来看一道基础的广度优先层序遍历问题吧！
剑指OfferII044.二叉树每层的最大值
https://leetcode-cn.com/problems/hPov7L/solution/shua-chuan-jian-zhi-offer-day21-dui-lie-vo9a5/
难度：中等
题目
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
提示：
- 二叉树的节点个数的范围是 [0,10 ^ 4]
- -2 ^ 31 <= Node.val <= 2 ^ 31 - 1
示例
示例1： 输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9] 解释: 1 / \ 3 2 / \ \ 5 3 9 示例2： 输入: root = [1,2,3] 输出: [1,3] 解释: 1 / \ 2 3 示例3： 输入: root = [1] 输出: [1] 示例4： 输入: root = [1,null,2] 输出: [1,2] 解释: 1 \ 2 示例5： 输入: root = [] 输出: []
分析
题目要求我们获取每一层的最大值，正好满足队列的出入队操作。
- 首先我们需要初始化队列queue、及返回队列ret
- 当队列不为空时，循环执行出入队
- 访问每一层前，初始化num为最小值
- 然后比较获取当前队列中的val最大值，并将最大值加入ret中
- 根据每个出队的节点，判断该节点的左、右子树是否存在，若存在则执行入队操作
- 循环3--5步骤，直到队列为空停止，并返回ret即可
解题
Python:
class Solution: def largestValues(self, root): ret, queue = [], deque() if root: queue.append(root) while queue: num = -float('inf') for i in range(len(queue)): q = queue.popleft() num = max(num, q.val) if q.left: queue.append(q.left) if q.right: queue.append(q.right) ret.append(num) return ret
Java:
class Solution { public List<Integer> largestValues(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<Integer> ret = new LinkedList<>(); if (root != null) { queue.add(root); } while (!queue.isEmpty()) { int num = Integer.MIN_VALUE; int lg = queue.size(); for (int i = 0; i < lg; i++) { TreeNode q = queue.poll(); num = Math.max(num, q.val); if (q.left != null) { queue.add(q.left); } if (q.right != null) { queue.add(q.right); } } ret.add(num); } return ret; } }
通过上面的题目，我们可以发现，只是条件判断略有不同，而代码总体没有太大的差别。不信，再来看看下面的题目吧。
剑指OfferII045.二叉树最底层最左边的值
https://leetcode-cn.com/problems/LwUNpT/solution/shua-chuan-jian-zhi-offer-day21-dui-lie-do26g/
难度：中等
题目
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
提示:
- 二叉树的节点个数的范围是 [1,10 ^ 4]
- -2 ^ 31 <= Node.val <= 2 ^ 31 - 1
示例：
示例 1: 输入: 2 / \ 1 3 输出: 1 示例 2: 输入: 1 / \ 2 3 / / \ 4 5 6 / 7 输出: 7
分析
首先，最简单的应该是BFS逐层遍历
- 我们创建一个变量ret，用于记录每行的第一个val
- 然后创建队列queue，由于题目说明至少有一个节点，则root无脑入队，开始while循环
- 判断每行的第一个节点，将ret变量更新为首个节点的值
- 直到队列为空时，终止循环，返回ret即可。
解题
Python:
class Solution: def findBottomLeftValue(self, root): queue = deque([root]) ret = root.val while queue: for i in range(len(queue)): q = queue.popleft() if i == 0: ret = q.val if q.left: queue.append(q.left) if q.right: queue.append(q.right) return ret
Java:
class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int ret = root.val; while (!queue.isEmpty()) { int lg = queue.size(); for (int i = 0; i < lg; i++) { TreeNode q = queue.poll(); if (i == 0){ ret = q.val; } if (q.left != null) { queue.add(q.left); } if (q.right != null) { queue.add(q.right); } } } return ret; } }
最后再来看一道类似的题目吧，通过这三道二叉树的广度优先搜索题目，相信大家对于这方面的知识点，可以完全掌握了。
剑指OfferII046.二叉树的右侧视图
https://leetcode-cn.com/problems/WNC0Lk/solution/shua-chuan-jian-zhi-offer-day21-dui-lie-n360i/
难度：中等
题目
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
提示:
- 二叉树的节点个数的范围是 [0,100]
- -100 <= Node.val <= 100
示例
示例 1: 1 / \ 2 3 \ \ 5 4 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入: [] 输出: []
分析
这道题，使用简单的BFS逐层遍历即可解题
- 我们创建一个列表ret，用于记录每行的最右节点的val
- 然后创建队列queue，当root不为空时，将root加入队列，然后开始while循环
- 判断每行的最后一个节点，并将该节点的值加入ret列表中
- 根据每个出队的节点，判断该节点的左、右子树是否存在，若存在则执行入队操作
- 直到队列为空时，终止循环，返回ret即可
解题
Python:
class Solution: def rightSideView(self, root): queue, ret = deque(), [] if root: queue.append(root) while queue: lg = len(queue) for i in range(lg): q = queue.popleft() if i == lg - 1: ret.append(q.val) if q.left: queue.append(q.left) if q.right: queue.append(q.right) return ret
Java:
class Solution { public List<Integer> rightSideView(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if (root != null) { queue.add(root); } List<Integer> ret = new LinkedList<>(); while (!queue.isEmpty()) { int lg = queue.size(); for (int i = 0; i < lg; i++) { TreeNode q = queue.poll(); if (i == lg - 1) { ret.add(q.val); } if (q.left != null) { queue.add(q.left); } if (q.right != null) { queue.add(q.right); } } } return ret; } }
关于队列的题目，就介绍到这里，当然通过二叉树的广度优先搜索，也引入了树这个概念。明天，我们就该进入树这章的专题了！
to be continue......
