二叉搜索树的众数(力扣501)

题目如下:

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1:

输入:root = [1,null,2,2]
输出:[2]

示例 2:

输入:root = [0]
输出:[0]

提示:

  • 树中节点的数目在范围 [1, 104] 内
  • -105 <= Node.val <= 105

解题思路如下:直接暴力的算法就是遍历一遍树然后用map记录,最后再对map里的频率进行排序。但是这颗树是二叉搜索树,所以我们要利用好特性,在中序遍历的同时,设置变了count和maxTime来记录下出现的次数,其中当count大于maxTime时就可以动态改变最大值,而当相等时就把该数弹进容器里

代码实现如下:

class Solution {

public:

     int count=0;int maxSize=0;TreeNode*pre=nullptr;vector<int>result;

     void  travel(TreeNode*cur){

        if(cur==nullptr)return;

        travel(cur->left);

        if(pre==nullptr){count=1;}//是空的话说明cur遍历到叶子了

        else if(pre->val==cur->val){count++;}

        else {count=1;}

        pre=cur;//第一次

        if(count==maxSize){

            result.push_back(cur->val);

        }

        if(count>maxSize){

            maxSize=count;

            result.clear();

            result.push_back(cur->val);

        }travel(cur->right);

     }

     

    vector<int> findMode(TreeNode* root) {

      travel(root);

      return result;

    }

};

相关推荐

  1. 501

    2024-04-25 05:56:08       26 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-25 05:56:08       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-25 05:56:08       100 阅读
  3. 在Django里面运行非项目文件

    2024-04-25 05:56:08       82 阅读
  4. Python语言-面向对象

    2024-04-25 05:56:08       91 阅读

热门阅读

  1. 基于单片机的红外无线测距仪

    2024-04-25 05:56:08       35 阅读
  2. HarmonyOS —— 跳转应用详情页

    2024-04-25 05:56:08       40 阅读
  3. sparkctl x86/arm不同平台编译使用

    2024-04-25 05:56:08       32 阅读
  4. PyTorch库中item()函数的作用(python)

    2024-04-25 05:56:08       33 阅读
  5. python安装第三方包

    2024-04-25 05:56:08       34 阅读
  6. 搭建最新tensorflow 与pytorch环境

    2024-04-25 05:56:08       37 阅读
  7. 本地wsl的Ubuntu安装docker,不使用docker桌面版

    2024-04-25 05:56:08       38 阅读
  8. spring的扩展接口

    2024-04-25 05:56:08       36 阅读
  9. python实现爬虫例子2

    2024-04-25 05:56:08       27 阅读