N叉树的层序遍历
- 思路：
采用广度优先搜索（BFS）实现N叉树的层序遍历。其核心思路是通过队列逐层处理节点：首先将根节点入队，循环中每次处理一层的所有节点。具体步骤为：记录当前层的节点数 sz，遍历 sz 次，每次取出队首节点并将其值存入临时数组中，同时将该节点的所有非空子节点按顺序入队，确保下一层节点被正确记录。处理完该层的所有节点后，将临时数组加入结果集，重复此过程直到队列为空。最终，结果集按层次顺序存储所有节点的值，实现了层序遍历的分层输出。
（这个题目也可以当做BFS的模板题进行记忆）
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(auto child : t->children) {
if(child != nullptr) // 只有非空的子节点才入队
q.push(child);
}
}
// 将当前层的节点值加入最终结果数组
ret.push_back(tmp);
}
// 返回最终的层序遍历结果
return ret;
}
};
二叉树锯齿形层序遍历
- 思路：
通过层序遍历（广度优先搜索）实现二叉树的之字形层次遍历。首先初始化一个队列存储当前层的节点，然后逐层遍历每个节点，按层次顺序将节点值存入临时数组。在偶数层，使用 reverse 反转当前层的节点顺序。每层的节点值存储到结果数组 ret 中，最终返回该结果。flag 用于标记当前层的奇偶性，以决定是否需要反转该层的节点顺序。
class Solution
{
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root)
{
// 结果存储二维数组，每一层的节点值存放在一个内层数组中
vector<vector<int>> ret;
// 使用队列来辅助层序遍历
queue<TreeNode*> q;
// 如果根节点为空，直接返回空的结果
if(root == nullptr) return ret;
// 将根节点入队，开始层序遍历
q.push(root);
// 标志位，用来控制层级的遍历顺序（zigzag的实现）
int flag = 1;
// 进行层序遍历
while(q.size())
{
// 当前层的节点数量
int sz = q.size();
// 临时数组，用来存储当前层的节点值
vector<int> tmp;
// 遍历当前层的所有节点
for(int i = 0; i < sz; i++)
{
TreeNode* 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(flag % 2 == 0) reverse(tmp.begin(), tmp.end());
// 将当前层的节点值加入最终结果数组
ret.push_back(tmp);
// 改变标志位，用于控制下一层的遍历顺序
flag++;
}
// 返回最终的zigzag层序遍历结果
return ret;
}
};
二叉树最大宽度
- 思路：
通过层序遍历计算二叉树的最大宽度，使用队列存储节点和它们的编号。每个节点的编号根据完全二叉树的规则分配，根节点为1，左子节点编号为 2 * 父节点编号，右子节点编号为 2 * 父节点编号 + 1。每次遍历一层时，计算该层的宽度，即最右节点和最左节点的编号差加1，更新最大宽度。最后返回最大宽度作为结果。
class Solution
{
public:
int widthOfBinaryTree(TreeNode* root)
{
// 使用一个队列来存储节点以及节点的位置编号
vector<pair<TreeNode*, unsigned int>> q;
// 将根节点和编号1入队
q.push_back({root, 1});
// 初始化最大宽度为0
unsigned int ret = 0;
// 当队列不为空时，进行层序遍历
while(q.size())
{
// 获取当前层最左边和最右边节点的位置编号
auto& [x1, y1] = q[0]; // 获取最左边节点
auto& [x2, y2] = q.back(); // 获取最右边节点
// 更新最大宽度，当前层的宽度是最右边节点编号 - 最左边节点编号 + 1
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, 2 * y}); // 左子节点的编号为2*y
if(x->right) tmp.push_back({x->right, 2 * y + 1}); // 右子节点的编号为2*y+1
}
// 更新队列为下一层的节点和编号
q = tmp;
}
// 返回最大宽度
return ret;
}
};
在每个树行中找最大值
- 思路：
通过层序遍历计算每一层的最大值。首先，初始化一个队列存储节点并将根节点入队。对于每一层，记录该层的节点数，遍历该层的每个节点，并更新当前层的最大值。每次遍历完一层后，将该层的最大值加入结果数组 ret。最后返回包含每层最大值的数组 ret。
class Solution
{
public:
vector<int> largestValues(TreeNode* root)
{
vector<int> ret; // 用于存储每一层的最大值
queue<TreeNode*> q; // 用队列进行层序遍历
if(root == nullptr) return ret; // 如果根节点为空，直接返回空结果
q.push(root); // 将根节点入队
// 使用广度优先搜索（BFS）逐层遍历二叉树
while(q.size())
{
int sz = q.size(); // 当前层的节点数量
int tmp = INT_MIN; // 用于记录当前层的最大值，初始化为最小整数
// 遍历当前层的每个节点
for(int i = 0; i < sz; i++)
{
TreeNode* 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; // 返回包含每层最大值的数组
}
};
最后一块石头
- 思路：
简单题想到用堆即可解决。
class Solution
{
public:
int lastStoneWeight(vector<int>& stones)
{
// 创建一个大根堆（优先队列），用于存储石头的重量
priority_queue<int> heap;
// 将所有石头的重量放入大根堆中
for(auto x : stones) heap.push(x);
// 当堆中有多于一个石头时，继续碰撞
while(heap.size() > 1)
{
// 取出堆顶的两个最大石头
int a = heap.top(); // 最大石头
heap.pop();
int b = heap.top(); // 第二大石头
heap.pop();
// 计算这两个石头碰撞后的结果
if(a > b)
heap.push(a - b); // 如果一个石头大于另一个，将差值重新放入堆中
}
// 如果堆中有石头，则返回堆顶的石头重量；否则返回0
return heap.size() ? heap.top() : 0;
}
};
数据流中的第K大元素
- 思路：
通过使用一个大小为 k 的小根堆来高效地维护当前的第 k 大元素。构造函数中，将输入数组 nums 中的元素逐个加入小根堆，确保堆中只保留前 k 个最大的元素。当堆的大小超过 k 时，移除堆顶元素，这样堆顶始终保存着第 k 大的元素。add 方法每次添加新元素时，也将其插入堆中，并确保堆的大小不超过 k，最后返回堆顶元素作为当前的第 k 大元素。这样可以在 O(log k) 的时间复杂度内高效地处理动态数据流。
class KthLargest
{
priority_queue<int, vector<int>, greater<int>> heap;
int _k; // 用于存储k，表示我们关心的是第k大的元素
public:
// 构造函数：初始化时将nums中的元素逐个加入堆中
KthLargest(int k, vector<int>& nums)
{
_k = k; // 保存k的值
// 将nums中的每个元素逐个加入堆中
for(auto x : nums)
{
heap.push(x); // 将元素放入小根堆
// 如果堆的大小超过k，移除堆顶元素，保持堆的大小为k
if(heap.size() > _k) heap.pop();
}
}
// add方法：每次添加一个新数字并返回当前的第k大的元素
int add(int val)
{
heap.push(val); // 将新元素放入小根堆中
// 如果堆的大小超过k，移除堆顶元素，确保堆中只有前k个最大的元素
if(heap.size() > _k) heap.pop();
// 返回堆顶元素，它就是当前第k大的元素
return heap.top();
}
};
前K个高频单词
- 思路：
使用哈希表统计每个单词的出现频率，并通过一个小根堆来维护频率最高的 k 个单词。首先，将每个单词及其频次存入哈希表。然后，遍历哈希表中的每个元素，将其插入到小根堆中，堆的大小始终保持为 k，如果堆的大小超过 k，就弹出堆顶元素。最后，从堆中依次取出 k 个元素并按顺序返回，堆顶的元素是频率最高的单词，若频次相同，则按字典顺序排序。
class Solution
{
// 定义一个pair，表示单词和它的频次
typedef pair<string, int> PSI;
// 自定义比较器用于小根堆排序：首先根据频次排序，其次根据字典顺序排序
struct cmp
{
bool operator()(const PSI& a, const PSI& b)
{
// 如果频次相等，按字典顺序排序
if(a.second == b.second)
return a.first < b.first;
// 否则按频次从大到小排序
return a.second > b.second;
}
};
public:
// topKFrequent方法：返回出现频率最高的k个单词
vector<string> topKFrequent(vector<string>& words, int k)
{
unordered_map<string, int> hash; // 用unordered_map统计每个单词的出现次数
for(auto& x : words)
hash[x]++; // 统计每个单词的频次
priority_queue<PSI, vector<PSI>, cmp> heap; // 创建一个小根堆，排序根据频次和字典顺序
// 将每个单词及其频次推入堆中
for(auto psi : hash)
{
heap.push(psi); // 推入堆中
// 如果堆的大小超过k，弹出堆顶元素，保证堆中只存储前k个频率最高的单词
if(heap.size() > k)
heap.pop();
}
vector<string> ret(k); // 用于存储结果的数组
// 从堆中弹出前k个元素，按从频率高到低顺序存储到结果数组中
for(int i = k - 1; i >= 0; i--)
{
ret[i] = heap.top().first; // 获取堆顶元素的单词
heap.pop(); // 弹出堆顶元素
}
return ret; // 返回结果数组
}
};
数据流中的中位数
- 思路：
使用两个堆来维持数据的中位数：一个大根堆 left 用于存储较小的一半数，另一个小根堆 right 用于存储较大的一半数。每次添加一个新数字时，通过比较数字与当前堆顶的值来决定将其插入到哪个堆中，并保持两个堆的大小平衡：要么两个堆大小相等，要么左堆比右堆多一个元素。在查找中位数时，如果两个堆大小相等，中位数是两堆顶元素的平均值；如果堆大小不等，中位数是左堆的堆顶元素（最大值）。这种方法能在 O(log N) 的时间复杂度内高效地处理动态数据流的中位数问题。
class MedianFinder
{
priority_queue<int> left; // 大根堆，用于存储较小的一半元素
priority_queue<int, vector<int>, greater<int>> right; // 小根堆，用于存储较大的一半元素
public:
// 构造函数
MedianFinder()
{}
// 添加一个新数字
void addNum(int num)
{
// 如果左堆和右堆的大小相等
if(left.size() == right.size())
{
// 如果左堆为空或者当前数字小于等于左堆的最大元素
if(left.empty() || left.top() >= num)
{
left.push(num); // 将数字放入左堆（大根堆）
}
else
{
// 否则，将数字放入右堆（小根堆），然后调整堆
right.push(num); // 将数字放入右堆（小根堆）
left.push(right.top()); // 从右堆取出最小值，放入左堆
right.pop(); // 从右堆中移除最小值
}
}
else
{
// 如果左堆的大小大于右堆
if(right.empty() || right.top() >= num)
{
left.push(num); // 将数字放入左堆（大根堆）
right.push(left.top()); // 从左堆取出最大值，放入右堆
left.pop(); // 从左堆中移除最大值
}
else
{
right.push(num); // 否则，将数字直接放入右堆（小根堆）
}
}
}
// 查找当前的中位数
double findMedian()
{
// 如果两个堆的大小相等，中位数是两堆顶元素的平均值
if(left.size() == right.size())
return static_cast<double>(left.top() + right.top()) / 2.0; // 返回浮点数结果
else
return left.top(); // 否则，中位数是左堆的最大元素
}
};