队列+宽搜(典型算法思想)—— OJ例题算法解析思路
目录
一、429. N 叉树的层序遍历 - 力扣(LeetCode)
算法代码:
1. Node 类定义
2. Solution 类与层序遍历函数
3. 初始化结果与队列
4. 开始层序遍历
5. 返回结果
总结
改进建议
二、103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode)
算法代码:
1. TreeNode 类定义
2. Solution 类与锯齿形层序遍历函数
3. 初始化结果与队列
4. 开始层序遍历
5. 判断是否逆序
6. 返回结果
总结
改进建议
主要改进:
三、662. 二叉树最大宽度 - 力扣(LeetCode)
算法代码:
1. TreeNode 类定义
2. Solution 类及其方法
3. 初始化结果与队列
4. 开始遍历树
5. 准备下一层节点
6. 返回结果
总结
改进建议
改动说明:
四、515. 在每个树行中找最大值 - 力扣(LeetCode)
算法代码:
1. TreeNode 类定义
2. Solution 类与方法
3. 初始化结果与队列
4. 开始遍历
5. 返回结果
总结
改进建议
主要改动
一、429. N 叉树的层序遍历 - 力扣(LeetCode)
算法代码:
/*
// 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; // 层序遍历需要的队列
if (root == nullptr)
return ret;
q.push(root);
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) // 让下⼀层结点⼊队
{
if (child != nullptr)
q.push(child);
}
}
ret.push_back(tmp);
}
return ret;
}
};
1. 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;
}
};
-
Node
类定义了 N 叉树的节点结构,每个节点包含一个整型值val
和一个子节点向量children
,用于存储该节点的所有子节点。 -
提供了三个构造函数:
-
默认构造函数。
-
接受一个值
_val
的构造函数。 -
接受一个值和一个子节点向量的构造函数。
-
2. Solution 类与层序遍历函数
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
-
定义了
Solution
类,并在其中实现了levelOrder
函数,该函数接受一个指向根节点的指针root
,并返回一个二维向量vector<vector<int>>
,表示层序遍历的结果。
3. 初始化结果与队列
vector<vector<int>> ret; // 记录最终结果
queue<Node*> q; // 层序遍历需要的队列
if (root == nullptr)
return ret;
q.push(root);
-
创建一个向量
ret
用于存储每层的节点值。 -
创建一个队列
q
用于实现 BFS。 -
如果
root
为nullptr
(即树为空),直接返回空的结果。 -
将根节点
root
入队。
4. 开始层序遍历
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) // 让下⼀层结点⼊队
{
if (child != nullptr)
q.push(child);
}
}
ret.push_back(tmp);
}
-
使用
while
循环,当队列q
不为空时继续遍历:-
int sz = q.size();
获取当前层节点的数量。 -
创建一个临时向量
tmp
用于存储当前层的节点值。 -
使用
for
循环遍历当前层的每个节点:-
从队列中取出当前节点
t
(q.front()
)并将其从队列中移除(q.pop()
)。 -
将节点
t
的值t->val
添加到tmp
中。 -
遍历当前节点的所有子节点
t->children
,将每个子节点(如果不为nullptr
)入队,以便在下一层处理。
-
-
将当前层的结果
tmp
添加到最终结果ret
中。
-
5. 返回结果
return ret;
-
最后,返回包含所有层节点值的二维向量
ret
。
总结
这段代码实现了 N 叉树的层序遍历,时间复杂度为 O(n),其中 n 是树中节点的数量,因为每个节点都被访问一次。空间复杂度为 O(m),其中 m 是树的最大宽度,因为在最坏情况下(例如完全平衡树),队列中可能会存储大量节点。
改进建议
-
使用更现代的 C++ 特性:可以使用
nullptr
代替NULL
(虽然这里已经用了),同时可以使用auto
关键字来简化代码。 -
检查子节点是否为
nullptr
:在此实现中,假设所有的子节点都已初始化为有效指针。如果子节点可以为nullptr
,则应确保在入队之前检查它们。 -
代码整洁性:可以考虑进一步提高代码的可读性,例如使用更具描述性的变量名。
以下是改进后的代码示例:
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ret; // 记录最终结果
queue<Node*> q; // 层序遍历需要的队列
if (root == nullptr) return ret; // 空树直接返回
q.push(root); // 将根节点入队
while (!q.empty()) {
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) { // 遍历子节点
if (child) q.push(child); // 非空子节点入队
}
}
ret.push_back(tmp); // 添加当前层结果
}
return ret; // 返回结果
}
};
二、103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode)
算法代码:
/**
* 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;
if (root == nullptr)
return ret;
queue<TreeNode*> q;
q.push(root);
int level = 1;
while (q.size()) {
int sz = q.size();
vector<int> tmp;
for (int i = 0; i < sz; i++) {
auto t = q.front();
q.pop();
tmp.push_back(t->val);
if (t->left)
q.push(t->left);
if (t->right)
q.push(t->right);
}
// 判断是否逆序
if (level % 2 == 0)
reverse(tmp.begin(), tmp.end());
ret.push_back(tmp);
level++;
}
return ret;
}
};
1. TreeNode 类定义
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) {}
};
-
TreeNode
结构体定义了二叉树的节点,包含一个整型值val
和指向左、右子节点的指针left
和right
。 -
提供了三个构造函数:
-
默认构造函数,初始化一个值为 0 的节点。
-
只接受一个整型值
x
的构造函数。 -
接受一个值以及左右子节点的构造函数。
-
2. Solution 类与锯齿形层序遍历函数
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
-
定义了
Solution
类,并在其中实现了zigzagLevelOrder
函数,该函数接受一个指向根节点的指针root
,并返回一个二维向量vector<vector<int>>
,表示锯齿形遍历的结果。
3. 初始化结果与队列
vector<vector<int>> ret;
if (root == nullptr)
return ret;
queue<TreeNode*> q;
q.push(root);
int level = 1;
-
创建一个向量
ret
用于存储每层的节点值。 -
检查根节点
root
是否为nullptr
,如果是,直接返回空的结果。 -
创建一个队列
q
用于实现层序遍历,并将根节点root
入队。 -
初始化层计数器
level
,初始值为 1。
4. 开始层序遍历
while (q.size()) {
int sz = q.size();
vector<int> tmp;
for (int i = 0; i < sz; i++) {
auto t = q.front();
q.pop();
tmp.push_back(t->val);
if (t->left)
q.push(t->left);
if (t->right)
q.push(t->right);
}
-
使用
while
循环,当队列q
不为空时继续遍历:-
获取当前层节点的数量
sz
。 -
创建一个临时向量
tmp
用于存储当前层的节点值。 -
使用
for
循环遍历当前层的每个节点:-
从队列中取出当前节点
t
(q.front()
)并将其从队列中移除(q.pop()
)。 -
将节点
t
的值t->val
添加到tmp
中。 -
将当前节点的左右子节点(如果存在)入队,以便在下一层处理。
-
-
5. 判断是否逆序
if (level % 2 == 0)
reverse(tmp.begin(), tmp.end());
ret.push_back(tmp);
level++;
-
检查当前层的层数
level
是否为偶数:-
如果是偶数层,则使用
reverse
函数反转tmp
中的元素,以实现从右到左的输出。
-
-
将当前层的结果
tmp
添加到最终结果ret
中。 -
增加层计数器
level
。
6. 返回结果
return ret;
-
最后,返回包含所有层节点值的二维向量
ret
。
总结
这段代码实现了对二叉树的锯齿形层序遍历,时间复杂度为 O(n),其中 n 是树中节点的数量,因为每个节点都被访问一次。空间复杂度为 O(m),其中 m 是树的最大宽度,因为在最坏情况下(例如完全平衡树),队列中可能会存储大量节点。
改进建议
-
使用更现代的 C++ 特性:可以使用
nullptr
代替NULL
(虽然这里已经用了),同时可以使用auto
关键字来简化代码。 -
优化反转操作:如果使用双端队列(
deque
),可以避免在偶数层时反转数组的开销,直接在队列的两端插入元素。 -
代码整洁性:可以考虑进一步提高代码的可读性,例如使用更具描述性的变量名。
以下是稍作修改和优化后的代码示例,使用双端队列来提高效率:
#include <vector>
#include <queue>
#include <deque> // 引入双端队列
using namespace std;
// 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;
if (root == nullptr)
return ret;
queue<TreeNode*> q;
q.push(root);
bool leftToRight = true; // 指示当前层是否从左到右
while (!q.empty()) {
int sz = q.size();
deque<int> tmp; // 使用双端队列保存当前层节点值
for (int i = 0; i < sz; i++) {
auto t = q.front();
q.pop();
if (leftToRight) {
tmp.push_back(t->val); // 从右侧插入
} else {
tmp.push_front(t->val); // 从左侧插入
}
if (t->left)
q.push(t->left);
if (t->right)
q.push(t->right);
}
ret.push_back(vector<int>(tmp.begin(), tmp.end())); // 将 deque 转换为 vector
leftToRight = !leftToRight; // 切换方向
}
return ret;
}
};
主要改进:
-
使用
deque
替代vector
,避免在偶数层时反转数组,提高了效率。 -
使用
leftToRight
布尔变量来指示当前层的遍历方向,使代码更清晰。
三、662. 二叉树最大宽度 - 力扣(LeetCode)
不采用下面硬来的方法,会超时:
算法代码:
/**
* 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});
unsigned int ret = 0;
while (q.size()) {
// 先更新这⼀层的宽度
auto& [x1, y1] = q[0];
auto& [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
// 让下⼀层进队
vector<pair<TreeNode*, unsigned int>> tmp; // 让下⼀层进⼊这个队列
for (auto& [x, y] : q) {
if (x->left)
tmp.push_back({x->left, y * 2});
if (x->right)
tmp.push_back({x->right, y * 2 + 1});
}
q = tmp;
}
return ret;
}
};
1. TreeNode 类定义
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) {}
};
-
TreeNode
结构体定义了二叉树的节点。每个节点包含一个整型值val
和指向左、右子节点的指针left
和right
。 -
包含构造函数,用于不同情况初始化节点。
2. Solution 类及其方法
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
-
定义了
Solution
类,并在其中实现了widthOfBinaryTree
方法,该方法接受一个指向根节点root
的指针,并返回树的最大宽度。
3. 初始化结果与队列
vector<pair<TreeNode*, unsigned int>> q; // 用数组模拟队列
q.push_back({root, 1}); // 用一个编号表示根节点
unsigned int ret = 0; // 记录最大宽度
-
创建一个向量
q
,用来存储二叉树节点及其相对位置(编号):-
pair<TreeNode*, unsigned int>
表示节点和其编号,编号用于计算宽度。
-
-
将根节点和编号
1
入队。 -
初始化
ret
为 0,用于保存最大宽度。
4. 开始遍历树
while (q.size()) {
// 先更新这层的宽度
auto& [x1, y1] = q[0];
auto& [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
-
使用
while
循环,直到队列q
为空:-
取出当前层的第一个节点
x1
和它的编号y1
,以及最后一个节点x2
和它的编号y2
。 -
通过计算
y2 - y1 + 1
更新最大宽度ret
。
-
5. 准备下一层节点
vector<pair<TreeNode*, unsigned int>> tmp; // 让下一层进队
for (auto& [x, y] : q) {
if (x->left)
tmp.push_back({x->left, y * 2}); // 左子节点的编号是父节点编号的两倍
if (x->right)
tmp.push_back({x->right, y * 2 + 1}); // 右子节点的编号是父节点编号的两倍加一
}
q = tmp; // 更新当前队列为下一层的节点
-
创建一个临时向量
tmp
用于存储下一层的节点及其相对位置。 -
遍历当前层的节点:
-
如果节点
x
有左子节点,将其和对应的编号(y * 2
)入队。 -
如果节点
x
有右子节点,将其和对应的编号(y * 2 + 1
)入队。
-
-
更新队列
q
为tmp
,以便在下一次循环中处理下一层。
6. 返回结果
return ret;
-
最后,返回最大宽度
ret
。
总结
这段代码有效地计算了二叉树的最大宽度,时间复杂度为 O(n),其中 n 是树中节点的数量,因为每个节点都被访问一次。空间复杂度为 O(m),其中 m 是树的最大宽度,最坏情况下队列可能存储一层的所有节点。
改进建议
-
内存管理:虽然此实现会使用较少的内存,但在某些情况下,可以考虑使用队列(如
std::queue
)而不是向量来管理节点,以提高效率和可读性。 -
错误处理:可以增加对无效输入(如空树)的处理逻辑。
-
代码可读性:在 C++17 及以上,可以使用
std::optional
或其他特性来进一步改善代码的表达力。
以下是稍作修改后的代码示例,使用 std::queue
来模拟队列,增强可读性:
#include <queue>
#include <utility> // 引入 std::pair
using namespace std;
// 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) {
if (root == nullptr) return 0; // 检查空树的情况
queue<pair<TreeNode*, unsigned int>> q; // 使用队列
q.push({root, 1}); // 根节点入队并设置初始编号
unsigned int ret = 0; // 记录最大宽度
while (!q.empty()) {
int sz = q.size();
auto [x1, y1] = q.front(); // 当前层第一个节点
auto [x2, y2] = q.back(); // 当前层最后一个节点
ret = max(ret, y2 - y1 + 1); // 更新最大宽度
// 将下一层的节点和它们的编号入队
for (int i = 0; i < sz; i++) {
auto [x, y] = q.front();
q.pop();
if (x->left) q.push({x->left, y * 2});
if (x->right) q.push({x->right, y * 2 + 1});
}
}
return ret; // 返回结果
}
};
改动说明:
-
使用
std::queue
来管理节点,而不是使用向量,增强了代码的可读性和逻辑清晰度。 -
添加了对空树的处理逻辑。
四、515. 在每个树行中找最大值 - 力扣(LeetCode)
算法代码:
/**
* 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<int> largestValues(TreeNode* root) {
vector<int> ret;
if (root == nullptr)
return ret;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
int sz = q.size();
int tmp = INT_MIN;
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);
}
return ret;
}
};
1. TreeNode 类定义
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) {}
};
-
TreeNode
结构体定义了二叉树的节点,每个节点包含一个整型值val
以及指向左、右子节点的指针left
和right
。 -
提供了三个构造函数,使得节点的创建更加灵活。
2. Solution 类与方法
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
-
Solution
类中的largestValues
方法接收一个指向根节点root
的指针,并返回一个整型向量vector<int>
,其中包含每一层的最大值。
3. 初始化结果与队列
vector<int> ret;
if (root == nullptr)
return ret; // 如果树为空,返回空向量
queue<TreeNode*> q;
q.push(root); // 将根节点入队
-
创建一个向量
ret
用于存储每层的最大值。 -
检查根节点
root
是否为nullptr
,如果是,直接返回空向量。 -
创建一个队列
q
用于执行广度优先搜索,并将根节点root
入队。
4. 开始遍历
while (q.size()) {
int sz = q.size(); // 当前层的节点数量
int tmp = INT_MIN; // 用于存储当前层的最大值
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); // 将当前层的最大值加入结果
}
-
使用
while
循环,当队列q
不为空时继续遍历:-
获取当前层的节点数量
sz
。 -
初始化
tmp
为INT_MIN
,用于存储当前层的最大值。 -
使用一个
for
循环遍历当前层的每个节点:-
取出队头节点
t
,并将其从队列中移除。 -
使用
max
函数更新当前层的最大值tmp
。 -
如果当前节点有左子节点,将其入队。
-
如果当前节点有右子节点,将其入队。
-
-
在每次完成当前层遍历后,将最大值
tmp
添加到结果向量ret
。
-
5. 返回结果
return ret;
-
最后,返回包含每层最大值的向量
ret
。
总结
这段代码有效地找出了每一层的最大值,时间复杂度为 O(n),其中 n 是树中节点的数量,因为每个节点都被访问一次。空间复杂度为 O(m),其中 m 是树的最大宽度,因为在最坏情况下队列中可能存储一层的所有节点。
改进建议
-
使用范围
for
循环:可以使用范围for
循环来简化代码,使代码更清晰。 -
处理无效输入:可以更明确地处理空树的情况,虽然当前实现已经涵盖了这点。
-
使用
nullptr
:在 C++11 及以上,使用nullptr
代替NULL
。
以下是稍作修改后的代码示例,使用范围 for
循环:
#include <vector>
#include <queue>
#include <limits.h> // 引入 INT_MIN
using namespace std;
// 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<int> largestValues(TreeNode* root) {
vector<int> ret;
if (root == nullptr)
return ret; // 如果树为空,返回空向量
queue<TreeNode*> q;
q.push(root); // 将根节点入队
while (!q.empty()) {
int sz = q.size(); // 当前层的节点数量
int tmp = INT_MIN; // 当前层的最大值
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); // 将当前层的最大值加入结果
}
return ret; // 返回结果
}
};
主要改动
-
增加了代码的可读性和整洁度,保持了功能的一致性。