专题13：广度优先搜索
题目559：N叉树的最大深度（YES）
- 解题思路：使用广度优先搜索，广度优先搜索的核心就是使用队列queue存储每个根节点，然后再存储孩子节点。
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int maxDepth(Node* root) {
if(root==NULL)
{
return 0;
}
//使用广度优先搜索，核心的点就是使用队列
queue<Node*>que;
que.push(root);
int high=0;
//不为空，就继续
while(!que.empty())
{
int size =que.size();
for(int i=0;i<size;i++)
{
Node*front=que.front();
que.pop();//出队
//添加孩子节点
int children_size=front->children.size();
for(int j=0;j<children_size;j++)
{
que.push(front->children[j]);
}
}
high++;
}
return high;
}
};
题目617：合并二叉树（NO）
- 解题思路：这题得用深度优先搜索，广度优先所搜过于繁琐。
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr) {
return t2;
}
if (t2 == nullptr) {
return t1;
}
auto merged = new TreeNode(t1->val + t2->val);
merged->left = mergeTrees(t1->left, t2->left);
merged->right = mergeTrees(t1->right, t2->right);
return merged;
}
};
题目965：单值二叉树（YES）
- 解题思路：使用二叉树的遍历算法进行判断就行，我这里用的是前序遍历，其实使用广度优先搜索也一样。
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void preorder(TreeNode*root,int ans,bool &sign)
{
if(root==NULL)
{
return ;
}
if(root->val!=ans)
{
sign=false;
}
preorder(root->left,ans,sign);
preorder(root->right,ans,sign);
}
bool isUnivalTree(TreeNode* root) {
//使用二叉树的遍历算法即可，这里用二叉树的前序遍历
int ans=root->val;
bool sign=true;
preorder(root,ans,sign);
return sign;
}
};
题目637：二叉树的层平均值（YES）
- 解题思路：使用层序遍历也就是广度优先搜索即可
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
//使用层序遍历，也就是广度优先搜索就行
queue<TreeNode*>que;
que.push(root);
vector<double>ans;
while(!que.empty())
{
int size=que.size();
double sum=0;
for(int i=0;i<size;i++)
{
TreeNode*front=que.front();
que.pop();
sum+=front->val;
//将孩子节点入队
if(front->left!=NULL)
{
que.push(front->left);
}
if(front->right!=NULL)
{
que.push(front->right);
}
}
ans.push_back(sum/size);
}
return ans;
}
};
题目175:计算二叉树的深度（YES）
- 解题思路：使用层序遍历
某公司架构以二叉树形式记录，请返回该公司的层级数。
- myself
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int calculateDepth(TreeNode* root) {
//使用层序遍历
if(root==NULL)
{
return 0;
}
queue<TreeNode*>que;
que.push(root);
int ans=0;
while(!que.empty())
{
int size=que.size();
ans++;
for(int i=0;i<size;i++)
{
TreeNode*front=que.front();
que.pop();
//将孩子节点入队
if(front->left!=NULL)
{
que.push(front->left);
}
if(front->right!=NULL)
{
que.push(front->right);
}
}
}
return ans;
}
};