算法_队列+宽度优先搜索---持续更新

前言

本文将会向你介绍有关队列+宽度优先搜索的题目：N叉树的层序遍历、二叉树最大宽度、在每个树中找最大值、二叉树的锯齿形层序遍历

N叉树的层序遍历

题目要求

题目解析

根据题意，需要把一个N叉树的节点值进行层序遍历并返回，层序遍历（按照树的层级顺序逐层访问每个节点，从上到下，从左到右进行遍历）
使用队列进行宽度优先搜索的原因：

1、先进先出：队列遵循先进先出原则，这跟我们从上到下每层依次遍历的访问顺序相符，先进先出就能确保每一层的节点都在前一层的节点之后被访问
2、动态管理节点：在遍历过程中，遍历该层节点结束，我们就需要移除该层节点，添加下一层节点，队列允许我们在遍历时将当前节点添加到队列的末尾，同时能从前端取下访问的节点
3、层级控制：通过使用队列，可以轻松控制当层的节点数量，可以将其子节点加入队列，并在处理完当前层的所有节点后再处理下一层的节点。

这道题也可以说是宽搜的模板，要求理解+记忆

总体思路（忽略一些细节）：
先将根节点加入到队列中，然后遍历该层的当前节点的所有子节点，并将被遍历到的节点pop并保存，然后将该层（根节点）的每个节点的子节点添加到队列当中，总的来说，就是先统计该层的节点，再统计该层节点的所有子节点，这样就能统计遍历出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:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> ret;    //保存每一层遍历的结果
        queue<Node*> q;
        q.push(root);
        if(root == nullptr) return ret;
        //将N叉树的节点加入到队列当中
        while(q.size())
        {
            int sz = q.size();
            vector<int> tmp;    //统计本层的节点
            for(int i = 0; i < sz; i++)
            {
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                //将该层的每一个节点的子节点加入到队列中
                for(Node* child : t->children)
                {
                    q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

二叉树最大宽度

题目要求

题目解析

代码如下

/**
 * 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 widthOfBinaryTree(TreeNode* root) 
    {
        vector<pair<TreeNode*, unsigned int>> q;    //用数组模拟队列，方便计算每层宽度
        q.push_back({root, 1});   //下标从1开始
        unsigned int ret = 0;   //最大宽度
        while(q.size())
        {
            //计算本层的宽度
            auto& [x1, y1] = q[0];  //提取pair
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);
            //将下一层添加到队列
            vector<pair<TreeNode*, unsigned int>> tmp;  //创建一个新队列存储下一层的节点
            for(auto& [x, y] : q)
            {
                if(x->right) tmp.push_back({x->right, y * 2});
                if(x->left) tmp.push_back({x->left, y * 2 + 1});
            }
            q = tmp;    
        }
        return ret;
    }
};

在每个树中找最大值

题目要求

题目解析

代码如下

class Solution {
public:
    vector<int> largestValues(TreeNode* root) 
    {
        queue<TreeNode*> q;
        vector<int> ret;   
        if(root == nullptr) return ret;
        q.push(root);
        while(q.size())
        {
            int tmp = INT_MIN;    //记录每一层的最大值(注意：节点的值可能取到-2^31
            //计算本层的最大值
            int sz = q.size();
            for(int i = 0; i < sz; i++)
            {
                auto t = q.front();
                q.pop();
                tmp = max(tmp, t->val);
                if(t->right) q.push(t->right);
                if(t->left) q.push(t->left);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

二叉树的锯齿形层序遍历

题目要求

题目解析

锯齿形层序遍历也就是在层序遍历的基础上：偶数反着来，奇数正常来
加一个标志位，用来表示该层是奇数层还是偶数层即可，具体思路与前些题相似，不再多赘述

代码如下

/**
 * 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<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        int flag = 1;     //标记奇数偶数行
        if(root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);
        //层序遍历
        while(q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for(int i = 0; i < sz; i++)
            {
                auto t = q.front(); //获取当前层的当前节点
                q.pop();
                if(flag % 2 != 0) 
                    tmp.push_back(t->val);
                else 
                    tmp.insert(tmp.begin(), t->val);
                //注意层序遍历需要先将左子节点入队，再将右子节点入队
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ret.push_back(tmp);
            flag++;
        }
        return ret;
    }
};