06树结构广度优先搜索
# 04 树结构广度优先搜索
# 广度优先搜索简介
广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因
此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时按照广的方向进行遍历的，也常常用来处理最短路径等问题。
考虑如下一颗简单的树。我们从 0 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，那么按照优先向着“广”的方向前进的策略，队列顶端的元素变化过程为 [0]->[1->2]->[3]，其中方括号代表每一层的元素。
树结构深度优先搜索编码模板：
void bfs(TreeNode* root) {
queue<TreeNode*> queue;
queue.push(root);
while (!queue.isEmpty()) {
auto node = queue.front();
queue.pop();
cout<<node->val;
if (node->left != null) {
queue.push(node->left);
}
if (node->right != null) {
queue.push(node->right);
}
}
}
# 102 二叉树的层序遍历 (opens new window)
给定一个二叉树，请返回其按 层序遍历 得到的节点值。
输入一个二叉树，输出一个二维数组表示二叉树的层序遍历结果。
输入：[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
输出:[[3],[9,20],[15,7]]
解析：
通常使用广度优先搜索进行层次遍历，使用一个队列存储当前层的所有节点。
在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数。
只要控制遍历这么多节点数，每遍历一个当前层的节点，将其出队列同时将其子节点入队列。
通过这种操作就能保证每次遍历的队列中都是当前层的节点，达到逐层遍历的目的。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root){
return ans;
}
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
int len = queue.size();
vector<int> levelNode;
// 逐层将下一层节点压入队列，保证队列中始终为同一层的节点
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
// 记录同一层节点值
levelNode.push_back(node->val);
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
}
// 将一层遍历结果加入结果集
ans.push_back(levelNode);
}
return ans;
}
};
# 107 二叉树的层序遍历 II (opens new window)
给定一个二叉树，请返回其节点值自底向上的 层序遍历 结果。
输入一个二叉树，输出一个二维数组表示二叉树的层序遍历结果。
输入：[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
输出:[[15,7],[9,20],[3]]
解析：
本题与102 二叉树的层序遍历 (opens new window)几乎没有差别。唯一的区别是本题要求从下到上输出每一层的节点值，所以只要对102题的过程稍作修改即可：在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。
在C++实现中，我们将102题的结果，使用reverse()方法将结果翻转即可。
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ans;
if(!root){
return ans;
}
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
int len = queue.size();
vector<int> levelNode;
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
levelNode.push_back(node->val);
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
}
ans.push_back(levelNode);
}
// 反转层次遍历结果
reverse(ans.begin(),ans.end());
return ans;
}
};
# 429 N 叉树的层序遍历 (opens new window)
给定一个 N 叉树，请返回其按 层序遍历 得到的节点值。
输入一个 N 叉树，输出一个二维数组表示 N 叉树的层序遍历结果。
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
解析：
本题与102 二叉树的层序遍历 (opens new window)的思路一致，区别在于 N 叉树每个非叶子节点有多个子节点，但是本质上并没有什么差别。在二叉树的广度优先遍历中，我们使用两个if语句判断是否存在左右节点；在 N 叉树中我们只需要使用一个循环判断存在的所有子节点即可。
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
if(!root){
return ans;
}
queue<Node*> queue;
queue.push(root);
while(!queue.empty()){
int len = queue.size();
vector<int> levelNode;
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
levelNode.push_back(node->val);
for(auto ch_node:node->children){
queue.push(ch_node);
}
}
ans.push_back(levelNode);
}
return ans;
}
};
# 199 二叉树的右视图 (opens new window)
给定一个二叉树的 根节点 root，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入一个二叉树，输出一个数组表示从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
解析：
本题也是二叉树层次遍历的一种应用，所谓的右视图其实就是层次遍历中每一层的最右侧元素构成的。所以我们还是使用层次遍历，在每一层的遍历过程中，保留最右侧元素值。
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if(!root){
return ans;
}
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
int len = queue.size();
int rsh_node;
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
rsh_node = node->val;
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
}
ans.push_back(rsh_node);
}
return ans;
}
};
# 515 在每个树行中找最大值 (opens new window)
给定一棵二叉树的根节点 root ，找出该二叉树中每一层的最大值。
输入一个二叉树，输出一个数组表示二叉树每层的最大值。
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/ \
3 2
/ \ \
5 3 9
解析：
本题还是使用广度优先搜索实现层次遍历，在每一层遍历中记录该层最大值即可。
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ans;
if(!root){
return ans;
}
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
int len = queue.size();
int maxElem = INT_MIN;
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
maxElem = max(maxElem,node->val);
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
}
ans.push_back(maxElem);
}
return ans;
}
};
# 637 二叉树的层平均值 (opens new window)
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
输入一个二叉树，输出一个数组表示二叉树每层的平均值。
输入：
3
/ \
9 20
/ \
15 7
输出：[3, 14.5, 11]
解释：第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
解析：
本题还是使用广度优先搜索实现层次遍历，在每一层遍历中记录该层所有节点值之和并计算平均值即可。
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
if(!root){
return ans;
}
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
int len = queue.size();
double sum = 0;
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
sum += node->val;
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
}
ans.push_back(sum/len);
}
return ans;
}
};
# 116 填充每个节点的下一个右侧节点指针 (opens new window)
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
输入一个二叉树，输出一个填充next指针后的图。
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
解析：
本题我们也使用对二叉树进行层次遍历的方式解决，在层次遍历的过程中将我们将二叉树每一层的节点拿出来遍历并连接。
层次遍历基于广度优先搜索，它与广度优先搜索的不同之处在于，广度优先搜索每次只会取出一个节点来拓展，而层次遍历会每次将队列中的所有元素都拿出来拓展，这样能保证每次从队列中拿出来遍历的元素都是属于同一层的。
通过层序遍历我们可以获取二叉树每一层的节点，剩下的工作就是在每一层的遍历过程中修改每个节点的 next 指针，将队头节点的next指向到下一任队头；同时将当前层的左右节点压入队列，拓展下一层的新队列。
本题层序遍历的思路不要求二叉树是完美二叉树，所以本题代码可以直接用于117 填充每个节点的下一个右侧节点指针 II (opens new window)
class Solution {
public:
Node* connect(Node* root) {
if(!root){
return nullptr;
}
queue<Node*> queue;
queue.push(root);
while(!queue.empty()){
int len = queue.size();
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
// 队头出队列之后，将其next指向当前队头
if(i<len-1){
node->next = queue.front();
}
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
}
}
return root;
}
};
# 111 二叉树的最小深度 (opens new window)
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
输入一个二叉树，输出一个整数表示最小深度。
输入：root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
输出：2
解析：
深度问题使用深度优先搜索可以更加方便的解决，但是本题求的是最小深度，所以用广度优先搜索在一定程度上可以带来更高的效率。
我们仍用自上而下层次遍历的方式计算最小深度，当某一层中出现了没有叶子节点的节点值返回当前深度即为最小深度。
class Solution {
public:
int minDepth(TreeNode* root) {
int ans = 0;
if(!root){
return ans;
}
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
++ans;
int len = queue.size();
for(int i=0;i<len;++i){
auto node = queue.front();
queue.pop();
if(!node->left && !node->right){
return ans;
}
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
}
}
return ans;
}
};