彻底学懂BFS广度优先遍历（最全解）

大家好，欢迎来到IT知识分享网。

目录

广度优先遍历（层序遍历）

一、什么是广度优先遍历（BFS）

二、为什么要广度优先遍历

三、什么时候用BFS

四、简单的BFS演示 二叉树的层序遍历

五、通过队列 和 记录层数 来进行层序遍历

广度优先搜索：

广度优先遍历（层序遍历）

一、什么是广度优先遍历（BFS）

广度优先遍历（Breadth-First Search，BFS）是一种图形搜索算法，从图的某一特定顶点出发，首先访问其所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，如此一层一层地向外扩展，直到访问完所有顶点。在二叉树等数据结构中，BFS 通常按照从根节点开始，一层一层地横向遍历节点。

二、为什么要广度优先遍历

1. 探索图或树的结构：可以全面地了解图或树的整体结构，对于需要对整个结构进行分析的问题非常有用。
2. 寻找最短路径：在某些情况下，BFS 可以有效地找到从一个起始点到目标点的最短路径。因为 BFS 在访问每个节点时，都是先访问距离起始点最近的节点，再逐渐扩展到更远的节点。
3. 分层处理问题：对于具有层次结构的数据，如二叉树的层序遍历，可以清晰地按照层次进行处理，便于理解和分析问题。

三、什么时候用BFS

1. 当需要找到从一个起始点到目标点的最短路径时。
2. 对图或树进行分层处理，例如二叉树的层序遍历、图的按层遍历等。
3. 当问题可以通过逐层探索来解决时，比如在迷宫问题中，找到从起点到终点的最短路径。

四、简单的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; } }; 

如果一行行读代码真的能发现 这个代码写的真的很完美，思维很跳跃，能够将控制层数 ，每一层的数字的大小比较都做得完美，当然如果多加熟练的练习，能够想上去也不是问题！