【专题十三】队列 +宽搜

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

题单汇总链接：点击 → 题单汇总（暂时未整理，因为还没刷完）

429. N 叉树的层序遍历

题目链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/

优质解

思路：

• 怎么区分记录每一层的结果呢？
• 我们只需要多加一个变量，在队列中元素出队前，来统计队列中的元素个数（因为我们的下一层节点是在该层节点出队的时候加的）

代码：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        if(root == nullptr) return {};
        vector<vector<int>> ans;
        queue<Node*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> tmp;
            int n = q.size(); // 记录当前层节点的个数
            for(int i = 0; i < n; i++)
            {
                Node *cur = q.front();
                // 把当前节点的孩子节点入队
                if(!cur->children.empty())
                {
                    for(int j = 0; j < cur->children.size(); j++)
                        q.push(cur->children[j]);
                }
                tmp.push_back(cur->val);
                q.pop(); // 当前元素出队
            }
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(m)$，m 是树中节点最多的那一层的节点数

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

题目链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/

个人解

思路：

• 记录当前层是左往右还是右往左，然后reserve
• 也可以用双端队列

屎山代码：

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        if(!root) return {};
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        int flag = 1; // 0 表示: 从右往左, 1 表示: 从左往右
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; i++)
            {
                TreeNode *cur = q.front();
                tmp.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
                q.pop();
            }
            if(flag == 0)
            {
                reverse(tmp.begin(), tmp.end()); // 反转 tmp 变成从右往左
                flag = 1;
            }
            else
            {
                flag = 0;
            }
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(m)$

662. 二叉树最大宽度

题目链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/description/

优质解

思路：

// 本题只关注最大宽度而不关心节点本身
// 我们要想办法记录同层第一个非零节点 和 最后一个非零节点之间的宽度
// 我们可以利用二叉树的节点的下标关系
// 左孩子记录为 p_index * 2 ， 右孩子记录成 p_index * 2 + 1，最后同层的首位相减就是结果

代码：

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        unsigned long long ans = 1;
        vector<pair<TreeNode*, unsigned long long>> q;  // 本层节点: 本层的节点下标
        q.emplace_back(root, 1L);
        while(!q.empty())
        {
            vector<pair<TreeNode*, unsigned long long>> tmp;
            for(auto &[node, index]: q) // C++17 特性，结构化绑定
            {
                if(node->left) tmp.emplace_back(node->left, index * 2);
                if(node->right) tmp.emplace_back(node->right, index * 2 + 1);
            }
            ans = max(q.back().second - q.front().second + 1, ans);
            q = move(tmp);
        }
        return ans;
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

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

题目链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/

个人解

屎山代码：

class Solution {
public:
    vector<int> largestValues(TreeNode* root) 
    {
        vector<int> ans;
        vector<TreeNode*> arr; // 队列
        if(root) arr.emplace_back(root);
        while(!arr.empty())
        {
            vector<TreeNode*> tmp; // tmp 是下一层
            int t_max = INT_MIN;
            for(auto node: arr)
            {
                t_max = max(t_max, node->val); // 记录本层最大值
                if(node->left) tmp.emplace_back(node->left);
                if(node->right) tmp.emplace_back(node->right);
            }
            ans.push_back(t_max);
            arr = move(tmp);
        }
        return ans;
    }
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！