关于bfs

bfs又称宽搜，全称是“宽度优先遍历”，然后就是关于bfs的三个说法：“宽度优先搜索”，“宽度优先遍历”，“层序遍历”，这三个都是同一个东西，前面我们介绍了大量的深度优先遍历的题目已经衍生算法，对这类比较熟悉的

在前面讲解深搜之前，我们上一篇数据结构相关的文章是介绍栈的，也列举了一些与栈相关的题目：算法学习（十一）—— 栈-CSDN博客

纯队列的题目很少很少，队列这种数据结构大部分都是用来服务BFS算法的，所以我们就把BFS和队列放一起来介绍。

和深搜一样，宽搜不仅仅只应用在树形结构中，这篇文章只列举了部分在树中的应用，先熟悉下BFS算法，后面会再展开细讲 

部分OJ题详解

429. N叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode）

第一道题就是简单的开胃菜，题目很简单，就是按顺序返回每一层的节点，下面来分析下这道题：

• 绝大部分的bfs题的代码类系都差不多，相当于有一个模板。因为从左往右遍历第一层后，要再次从最左边的节点继续往下遍历，所以我们是需要借助队列这个数据结构的，因为队列是先进先出的，遍历最左边节点时需要记录下，以便往下一层遍历时能找到最左边节点
• 这第一题我们就详细一点介绍下层序遍历的步骤：
• ①先搞一个队列，然后如果根节点不为空，让根节点入队列
• ②然后就是一个循环，条件是队列不为空时，先拿出队头元素，把队头元素的所有孩子节点都入队列，然后pop掉队头元素，一直重复这步，直到队列为空，层序遍历完成‘
• ③然后就是统计元素的时机，每次遍历时，先统计下队列里有多少元素，因为此时队列里元素的个数刚好是这一层元素的个数，然后按照数量执行步骤②即可

class Solution 
{
public:
    queue<Node*> q;
    vector<vector<int>> ret;
    vector<vector<int>> levelOrder(Node* root) 
    {
        bfs(root);
        return ret;
    }
    void bfs(Node* root)
    {
        if(root == nullptr) return;
        q.push(root); //先把根节点入队列
        while(!q.empty())
        {
            int size = q.size(); //记录此时队列元素个数，该个数代表本层节点的个数
            vector<int> v;
            for(size_t i = 0; i < size; i++)
            {
                Node* cur = q.front(); //拿到队头元素
                q.pop();
                v.push_back(cur->val);
                for(auto e : cur->children) //依次把队头下一层节点入队列
                {
                    q.push(e);
                }
            }
            ret.push_back(v);
        }
    }
};

103. 二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

锯齿形遍历，就是先从左往右（包括根节点），再从右往左遍历，依次循环直到遍历完成，其它的和第一题是一样的：

• 只需要在上一道题的基础上稍加修改即可；只需要把偶数行的结果在添加进最终数组之前，逆序一下即可

class Solution 
{
    queue<TreeNode*> q;
    vector<vector<int>> ret;
    bool e = true;
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        bfs(root);
        return ret;
    }
    
    void bfs(TreeNode* root)
    {
        if(root == nullptr) return;
        q.push(root); //先把根节点入队列
        while(!q.empty())
        {
            int size = q.size();
            vector<int> v;
            for(size_t i = 0; i < size; i++)
            {
                TreeNode* cur = q.front(); //拿到队头元素
                q.pop();
                v.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            if(e == true)
            {
                ret.push_back(v);
                e = false;
            }
            else
            {
                reverse(v.begin(), v.end());
                ret.push_back(v);
                e = true;
            }
        }
    }
};

662. 二叉树的最大宽度

662. 二叉树最大宽度 - 力扣（LeetCode）

宽度定义为“最左节点和最右节点之间的距离”，在这道题中，将题目给的二叉树视作满二叉树，两端点中间会出现一些延申到这一层的空节点，并且这些空节点也计入长度，下面来分析下这道题：

解法一： 

• 解法一：硬来；由于空节点也要计入长度，如果遇到空节点，把空节点也加入到队列里，然后后面遇到空节点时，默认加两个空节点即可
• 但是这样搞会有问题，以示例二为例，由于9只有左孩子一个孩子，那么右孩子会当成空加入到队列，但是这样的话队列的长度就是8了，不符合要求；这个也可以解决，就是用一个变量empty，统计空节点的个数，比如从6开始，empty一直++，直到遇到不是空节点也就是7时，empty + 2就是我们需要的长度。这种解法理论可行，但是提交过后会超时，假设3000个节点，然后只有2两条路径，就是纯左边和右边一路干到底，那么这个时间复杂度就非常夸张了，如下图：
• 

解法二

• 解法二：利用数组存储二叉树的方式给节点编号；树是可以通过顺序的方式存储的，比如堆结构，就是用的数组形式
• 我们先回一下用数组存储二叉树：默认根节点的下标是从1开始计数，然后按照层次遍历的顺序依次遍历并且入数组。所以就可以发现一个规律，对于每个节点都有：“假设一个节点下标是x，那么它的左孩子下标是2x，右孩子下标是2x + 1”：
• 
• 所以我们仍然创建一个队列，但是队列不再存int了，而是存一个键值对pair，first表示这个节点的指针，second表示这个节点的编号，然后对于左右孩子的下标就按照上面的公式入队列
• 然后就是计算宽度，直接拿出队头和队尾的元素，然后让两个的下标相减再+1就是我们最终需要的值
• 细节一：如果再优化的话，我们可以直接用数组vector<pair<TreeNode*, int>>来代替队列，因为对于不同的语言对于队列的实现是不一样的，有的队列的容器可以查队头队尾，有的只能查队尾
• 细节二：下标又可能溢出，以解法一的极端情况为例，左右如果各有1500个节点，那么数量就是2的1500次方-1，这个数是非常大的，任何数据类型都存不下；但是当我们相减之后，即使结果溢出，结果也是正确的，因为数据的存储可以看作是一个环形的，比如char类型，如下图：
• 
• 整型也是同理，就算溢出，相减完之后结果依旧是正确的，但是C++中用int的话会直接报错，所以我们用无符号整数unsigned int来存下标就OK了；如果没想到用unsigned int，那么就可以用字符串来存这个数，然后最后减法的时候做一次高精度减法也是可以的

 

class Solution 
{
    vector<pair<TreeNode*, unsigned int>> v;
    unsigned int ret;
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        bfs(root);
        return ret;
    }
    void bfs(TreeNode* root)
    {
        v.push_back({root, 1}); //先把根节点放进去
        while(!v.empty())
        {
            auto& [x1, y1] = v[0]; //拿到首元素
            auto& [x2, y2] = v.back(); //拿到结尾元素
            ret = max(ret, y2 - y1 + 1);

            //遍历下一层
            vector<pair<TreeNode*, unsigned int>> tmp; //让下一层进入这个队列，然后覆盖掉前面那个即可
            for(auto& [x, y] : v)
            {
                if(x->left) tmp.push_back({x->left, y * 2});
                if(x->right) tmp.push_back({x->right, y * 2 + 1});
            }
            v = tmp; //覆盖
        }
    }
};

515. 在每个树行中找最大值

515. 在每个树行中找最大值 - 力扣（LeetCode）

题目很简单，就算让我们找出一棵树中每一行的最大值然后返回即可：

• 算法也很简单，就是在层序遍历的过程中，用一个变量记录下最大值，然后在进入下一次遍历之前记录一下最大值即可

class Solution 
{
    queue<TreeNode*> q;
    vector<int> ret;
public:
    vector<int> largestValues(TreeNode* root) 
    {
        bfs(root);
        return ret;
    }
    void bfs(TreeNode* root)
    {
        if(root == nullptr) return;
        q.push(root);
        while(!q.empty())
        {
            int tmp = INT_MIN;
            int sz = q.size();
            for(int i = 0; i < sz; i++)
            {
                auto t = q.front();
                q.pop();
                tmp = max(tmp, t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ret.push_back(tmp);
        }
    }
};