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

发布于:2025-03-14 ⋅ 阅读:(12) ⋅ 点赞:(0)

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