【高效算法解析：从树的遍历到数据流处理的经典题解】—— LeetCode

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

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

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

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

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

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;  // 返回结果数组
    }
};

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