算法打开13天

41.前 K 个高频元素

（力扣347题）

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解题思路

1. 题目要求我们从一个整数数组 nums 中找出出现频率最高的 k 个元素。为了实现这一目标，我们可以采用以下步骤：
   1. 统计频率： 使用一个哈希表（unordered_map）来统计每个数字的出现次数。遍历数组 nums，对于每个数字，将其在哈希表中的计数加一。这样，我们可以快速得到每个数字的出现频率。
   2. 维护小顶堆： 使用一个优先队列（priority_queue）来维护频率最高的 k 个元素。优先队列的第一个元素是根节点，即堆顶元素。默认情况下，std::priority_queue 是一个大顶堆，但通过自定义比较函数 mycomparison，我们可以将其转换为小顶堆。小顶堆的特性是堆顶元素是所有元素中最小的，这正好符合我们的需求，因为我们希望在堆中保留频率最高的 k 个元素。当堆的大小超过 k 时，弹出堆顶元素（频率最小的元素），从而保证堆中始终存储的是频率最高的 k 个元素。
   3. 提取结果： 将小顶堆中的元素依次弹出，并存入结果数组。由于小顶堆的特性，弹出的顺序是频率从小到大，因此需要从后向前填充结果数组。最终，结果数组中存储的就是频率最高的 k 个元素。

单调队列与优先队列的区别

首先，我们需要明确 单调队列 和 优先队列 是两种不同的数据结构，它们的行为和用途有所不同。

单调队列

• 单调队列通常用于处理滑动窗口问题，它维护一个单调递增或单调递减的队列。
• 单调队列的第一个元素通常是当前窗口的最小值或最大值。
• 单调队列的实现通常基于双端队列（std::deque），而不是基于堆。

优先队列

• 优先队列是一种基于堆的数据结构，通常用于维护一个动态集合，使得每次可以高效地访问和删除具有最高优先级的元素。
• 优先队列的根节点（堆顶元素）是所有元素中优先级最高的元素。
• 默认情况下，std::priority_queue 是一个大顶堆，即堆顶元素是所有元素中最大的。

大顶堆的定义

在大顶堆中：

• 根节点（堆顶元素）是所有元素中最大的。
• 对于任意节点 i，其子节点的值都小于或等于节点 i 的值。

代码

// 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
// 你可以按 任意顺序 返回答案。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

// 使用单调队列（基于小根堆（底层逻辑是完全二叉树）
class Solution
{
public:
    // 小顶堆(自定义比较函数)
    class mycomparison
    {
        // 重载比较运算符 std::less<T> 把默认的大顶堆变成小顶堆
    public:
        //  pair<int, int>是类模板
        bool operator()(const pair<int, int> & lhs, const pair<int, int> & rhs)
        {
            // 比较两个元素的频率，频率大的排在后面（小顶堆）
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int> &nums, int k)
    { // 使用哈希表统计每个数字出现的频率
        unordered_map<int, int> map;
        // 遍历数组，统计每个数字的出现次数
        for (int i = 0; i < nums.size(); i++)
        {
            // 遍历数组，统计每个数字的出现次数
            map[nums[i]]++;
        }

        // 定义一个小顶堆，用于存储频率最高的 k 个元素
        // std::priority_queue 默认是一个大顶堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que; // priority_queue优先队列

        // 遍历哈希表，将元素及其频率加入小顶堆
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++)
        {
            // 将当前元素及其频率加入堆
            pri_que.push(*it);
             // 如果堆的大小超过 k
            if(pri_que.size() > k)
            {
                pri_que.pop();
            }
        }
        // 将小顶堆中的元素依次弹出，存入结果数组
        vector<int> result(k);
        //    / 从后向前填充结果数组
        for(int i = k - 1;  i >= 0; i--)
        {
             // 获取堆顶元素的数字部分
            result[i] = pri_que.top().first;
            // 弹出堆顶元素
            pri_que.pop();

        }
        // 返回结果数组
        return result;
    }
};

• 时间复杂度: O(nlogk)
• 空间复杂度: O(n)

42.二叉树的前序遍历

（力扣94题）

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

**输入：**root = [1,null,2,3]

输出：[1,2,3]

解释：

示例 2：

**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：

示例 3：

**输入：**root = []

输出：[]

示例 4：

**输入：**root = [1]

输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

解题思路

前序遍历的顺序是“根-左-右”，即先访问根节点，然后递归遍历左子树，最后递归遍历右子树。实现前序遍历可以使用递归或**非递归（栈）**的方法。

递归方法

递归方法是最直观的实现方式，利用函数调用栈来实现遍历：

1. 访问根节点：将当前节点的值加入结果向量。
2. 递归左子树：对当前节点的左子树进行前序遍历。
3. 递归右子树：对当前节点的右子树进行前序遍历。
4. 终止条件：如果当前节点为空，直接返回。

递归方法的优点是代码简洁，但可能会受到递归深度的限制。

非递归方法（栈）

非递归方法使用显式的栈来模拟递归调用：

1. 初始化栈：将根节点压入栈。
2. 循环条件：当栈不为空时，执行以下操作：
   • 弹出栈顶节点，访问其值，并将其值加入结果向量。
   • 如果右子节点不为空，将其压入栈。
   • 如果左子节点不为空，将其压入栈。
3. 终止条件：栈为空时，遍历完成。

非递归方法的优点是避免了递归调用的开销，适合处理较深的树结构

代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
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(nullptr), right(nullptr) {}
};

class Solution
{
public:
    // 递归函数
    void traversak(TreeNode *cur, vector<int> &vec)
    {
        if (cur == nullptr)
        {
            return;
        }
        vec.push_back(cur->val);    // 当前节点
        traversak(cur->left, vec);  // 左
        traversak(cur->right, vec); // 右
    }

    // 前序遍历
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> result;
        traversak(root, result);
        return result;
    }
};
class Solution
{
public:
    // 前序遍历
    vector<int> preorderTraversal(TreeNode *root)
    {
        // 定义栈
        stack<TreeNode *> st;
        // 结果集
        vector<int> result;
        // 空节点 返回空
        if (root == NULL)
        {
            return result;
        }
        // 根节点压入栈
        st.push(root);
        while (!st.empty())
        {
            TreeNode *node = st.top(); // 根节点
            st.pop();
            result.push_back(node->val);
            if (node->right)
            {
                // 右（空节点不入栈
                st.push(node->right);
            }
            if (node->left)
            {
                // 左（空节点不入栈
                st.push(node->left);
            }
        }
        return  result;
    }
};

return 只是结束当前栈帧的执行，并返回到调用它的函数。它不会影响其他栈帧的执行

43.二叉树的后序遍历

（力扣145题）

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题思路

后序遍历的顺序是“左-右-根”，即先递归遍历左子树，然后递归遍历右子树，最后访问根节点。实现后序遍历可以使用递归或**非递归（栈）**的方法。

递归方法

递归方法是最直观的实现方式，利用函数调用栈来实现遍历：

1. 递归左子树：对当前节点的左子树进行后序遍历。
2. 递归右子树：对当前节点的右子树进行后序遍历。
3. 访问根节点：将当前节点的值加入结果向量。
4. 终止条件：如果当前节点为空，直接返回。

递归方法的优点是代码简洁，但可能会受到递归深度的限制。

非递归方法（栈）

非递归方法使用显式的栈来模拟递归调用：

1. 初始化栈：将根节点压入栈。
2. 循环条件：当栈不为空时，执行以下操作：
   • 弹出栈顶节点，访问其值，并将其值加入结果向量。
   • 如果左子节点不为空，将其压入栈。
   • 如果右子节点不为空，将其压入栈。
3. 反转结果集：由于栈的后进先出特性，最终结果需要反转。
4. 终止条件：栈为空时，遍历完成。

非递归方法的优点是避免了递归调用的开销，适合处理较深的树结构。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
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(nullptr), right(nullptr) {}
};

class Solution
{
public:
    // 递归函数
    void traversak(TreeNode *cur, vector<int> &vec)
    {
        if (cur == nullptr)
        {
            return;
        }
        traversak(cur->left, vec);  // 左
        traversak(cur->right, vec); // 右
        vec.push_back(cur->val);    // 当前节点
    }

    // 后序遍历
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> result;
        traversak(root, result);
        return result;
    }
};



class Solution
{
public:
    // 后序遍历
    vector<int> postorderTraversal(TreeNode *root)
    {
        // 定义栈
        stack<TreeNode *> st;
        // 结果集
        vector<int> result;
        // 空节点 返回空
        if (root == NULL)
        {
            return result;
        }
        // 根节点压入栈
        st.push(root);
        while (!st.empty())
        {
            TreeNode *node = st.top(); // 根节点
            st.pop();
            result.push_back(node->val);
            if (node->left)
            {
                // 左（空节点不入栈
                st.push(node->left);
            }
            if (node->right)
            {
                // 右（空节点不入栈
                st.push(node->right);
            }
            
        }
        // 反转结果集
        reverse(result.begin(), result.end());
        return  result;
    }
};