day25

【0347.前K个高频元素】

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map <int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        vector<int> result = (nums.size(), -1);
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            if (map[it] >= k) {
                result[j] == map[it];
                j++
            }
        }
        return result; 
    }
};

• 这道题 完全想不到用队列 更何况是优先队列---小顶堆—。—
• 上面代码也不能运行出来 还是暂时搁置下次再看

【144.二叉树的前序遍历】
【145.二叉树的后序遍历】
【94.二叉树的中序遍历】

• 先序遍历：

/**
 * Definition for a binary tree node.
 * 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(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode *root, vector<int> &result) {
        if (root == nullptr)
            return ;
        result.push_back(root->val);
        traversal(root->left, result);
        traversal(root->right, result);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

• 概念 一、深度遍历（前序、中序、后序， 前中后指的是根节点的位置） 二、层次遍历
• 看看标准代码

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

• 首先明白 递归三要素：1.输入输出（返回值）参数如何确定 2.结束条件如何确定 3.单层递归的逻辑如何确定

  • 1.输入输出（返回值）参数如何确定
    • 输入参数：（看主函数 了解到需要获得 vector类型的返回值，所以输入参数 除根节点外 需要有vector& result并且注意是取地址）因为要打印出前序遍历节点的数值 所以参数里需要传入vector在放节点的数值
    • 输出参数：（再看看 子函数需不需要返回值 不需要就是void 对应语句reurn 注意不要写return 0）除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void
  • 2.结束条件如何确定
    • 当前遍历的这个节点是空，表明本层递归结束，直接return
  • 3.单层递归逻辑如何确定
    • 看取哪个结点数值
    • 如果是先序遍历 则是要先取中节点的数值

• 一些代码语句上的问题

  • if (cur == NULL) return; 空NULL 都可 （不知道有区别没？）

  • vec.push_back(cur->val); 把结点元素值赋值给数组的写法 不需要下标i 而是用push_back函数

  • traversal(cur->left, vec); 别忘了子函数 要一致 输入参数别写少了

• 中序遍历

/**
 * Definition for a binary tree node.
 * 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(left), right(right) {}
 * };
 */
class Solution {
    void traversal(TreeNode *cur, vector<int>& result) {
        if (cur->left == NULL)
            return;
        result.push_back(cur->left->val);
        traversal(cur, result);
        traversal(cur->right,result);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result; 
        traversal(root, result);
        return result;
    }
};

• 没有真正明白 取值！！！！放中间，而不是指针放中间!!!!因为单层递归目的是取值！！！！！

/**
 * Definition for a binary tree node.
 * 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(left), right(right) {}
 * };
 */
class Solution {
    void traversal(TreeNode *cur, vector<int>& result) {
        if (cur == NULL)
            return;
        traversal(cur->left, result);
        result.push_back(cur->val);
        traversal(cur->right,result);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result; 
        traversal(root, result);
        return result;
    }
};

• 后序遍历

/**
 * Definition for a binary tree node.
 * 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(left), right(right) {}
 * };
 */
class Solution {
    void taversal(TreeNode* cur, vector<int>& result) {
        if (cur == NULL) return;
        taversal(cur->left, result);
        taversal(cur->right, result);
        result.push_back(cur->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        taversal(root, result);
        return result;
    }
};