昨日回顾
昨天，我们介绍了队列的基础知识，并分别学习了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......
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论