队列+宽搜（典型算法思想）——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; // 返回结果 } }; 主要改动

增加了代码的可读性和整洁度，保持了功能的一致性。