彻底学懂BFS广度优先遍历最全解
彻底学懂BFS广度优先遍历（最全解）
目录
广度优先遍历（层序遍历）
一、什么是广度优先遍历（BFS）
广度优先遍历（Breadth-First Search，BFS）是一种图形搜索算法，从图的某一特定顶点出发，首先访问其所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，如此一层一层地向外扩展，直到访问完所有顶点。在二叉树等数据结构中，BFS 通常按照从根节点开始，一层一层地横向遍历节点。
二、为什么要广度优先遍历
- 探索图或树的结构：可以全面地了解图或树的整体结构，对于需要对整个结构进行分析的问题非常有用。
- 寻找最短路径：在某些情况下，BFS 可以有效地找到从一个起始点到目标点的最短路径。因为 BFS 在访问每个节点时，都是先访问距离起始点最近的节点，再逐渐扩展到更远的节点。
- 分层处理问题：对于具有层次结构的数据，如二叉树的层序遍历，可以清晰地按照层次进行处理，便于理解和分析问题。
三、什么时候用BFS
- 当需要找到从一个起始点到目标点的最短路径时。
- 对图或树进行分层处理，例如二叉树的层序遍历、图的按层遍历等。
- 当问题可以通过逐层探索来解决时，比如在迷宫问题中，找到从起点到终点的最短路径。
四、简单的BFS演示 二叉树的层序遍历
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}五、通过队列 和 记录层数 来进行层序遍历
这个题目真的很有意义，一定要耐心看完，我觉得肯定会对你有所提升。
对于普通的层序遍历，二叉树只是队列入节点，在增加节点，但是这里又要考虑层数的控制，每层数值的比较，是思维更加跳跃灵活的体现。
一定要自己先了解题目，尝试怎么根据层序遍历，来控制层数和每一层的数的奇偶比较。
解析真的写的很详细了：
广度优先搜索：
由于判断一棵二叉树是否为奇偶树的条件是针对同一层的节点，因此可以使用广度优先搜索，每一轮搜索访问同一层的全部节点，且只会访问这一层的节点。
使用队列存储节点。初始时，将根节点加入队列。每一轮搜索之前，队列中的节点是同一层的全部节点，记队列的大小为 size，该轮搜索只访问 size 个节点，即可保证该轮搜索访问的恰好是同一层的全部节点。搜索过程中，将当前层的节点的非空子节点依次加入队列，用于下一层的搜索。
判断一棵二叉树是否为奇偶树，需要考虑两个条件 ，一是节点值的奇偶性，二是节点值的单调性， 这两个条件都由层下标的奇偶性决定。因此，需要维护搜索到的层下标，以及对于 每一层搜索都需要维护上一个节点值 。
如果当前层下标是偶数，则要求当前层的所有节点的值都是奇数，且节点值从左到右严格递增。如果遇到节点值是偶数，或者当前节点值小于等于上一个节点值，则二叉树一定不是奇偶树。
如果当前层下标是奇数，则要求当前层的所有节点的值都是偶数，且节点值从左到右严格递减。如果遇到节点值是奇数，或者当前节点值大于等于上一个节点值，则二叉树一定不是奇偶树。
如果二叉树的所有节点都满足奇偶树的条件，则二叉树是奇偶树。
/**
* 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:
queue<TreeNode*> q;
bool isEvenOddTree(TreeNode* root) {
q.push(root);
int level=0;//根 0层
while(!q.empty())
{
int size=q.size();
int prev=level%2==0?INT_MIN:INT_MAX;//偶数层递增 奇数层递减 (同一层的上一个节点值进行比较)
for(int i=0;i<size;i++)
{
TreeNode* node=q.front();
int value=q.front()->val;
q.pop();
if(level%2==value%2) return false; //层数跟数的奇偶相反
if((level%2==0&&value<=prev)||(level%2==1&&value>=prev)) return false;
prev=value;
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
level++;
}
return true;
}
};如果一行行读代码真的能发现 这个代码写的真的很完美，思维很跳跃，能够将控制层数 ，每一层的数字的大小比较都做得完美，当然如果多加熟练的练习，能够想上去也不是问题！