当前位置：首页 > news >正文

【专题十三】队列 +宽搜

news 2025/7/23 14:40:13

📝前言说明：

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

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

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

点击链接	开始学习
双指针(1)	双指针(2)
双指针(3)	双指针(4)
滑动窗口(1)	滑动窗口(2)
滑动窗口(3)	滑动窗口(4)
二分查找(1)	二分查找(2)
前缀和(1)	前缀和(2)
前缀和(3)	位运算(1)
位运算(2)	模拟算法
快速排序	归并排序
链表	哈希表
字符串	栈
队列 + 宽搜	优先级队列
BFS 解决 FloodFill	BFS 解决最短路径
多源 BFS	BFS 解决拓扑排序

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

题目

429. N 叉树的层序遍历
- 优质解
103. 二叉树的锯齿形层序遍历
- 个人解
662. 二叉树最大宽度
- 优质解
515. 在每个树行中找最大值
- 个人解

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;}
};