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(); // 否则,中位数是左堆的最大元素
}
};