微信小程序实战教程 reactjs oracle dataframe security magento vue异步加载组件 vue特点 less比较级 android入门实例 centos查看python版本 matlab插值函数 centos定时任务 python开发教程 python获取数据类型 配置python环境 数据结构java版 java获取url javascript实例 tmac修改器 视频加字幕软件哪个好 infopath下载 淘宝自动发货软件 摩斯密码在线翻译 js日期格式化 工信部手机入网查询 不屑表情包 polyworks cmd命令数字雨 茸好珠 img写盘工具 js递归函数 flushdns 思源黑体 图片文字提取软件 nginx启动命令 大数据就业方向 取小数点后两位函数 firework软件 网页flash抓取器
当前位置: 首页 > 学习教程  > 编程语言

[leetCode]501. 二叉搜索树中的众数

2020/11/4 14:48:22 文章标签:

题目 链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree 给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。 假定 BST 有如下定义: 结点…

题目

链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

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

例如:
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2
返回[2].

提示:如果众数超过1个,不需考虑输出顺序

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

递归

思路:由于二叉树是有序的因此可以使用二叉树的中序遍历,使用一个pre指针保存当前节点的前一个节点,利用变量count进行计数,计数值如果等于最大的频率则将当前元素添加入列表当中,如果当前计数值大于最大的频率值则更新最大频率值,并且需要将列表清空,因为此时列表中的元素已经不再是众数了。

class Solution {

    // 记录前一个指针
    private TreeNode pre = null;

    // 计算出现次数
    private int count = 0;

    // 最大的出现频率
    private int maxCount = 0;

    private List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        searchBST(root);
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private void searchBST(TreeNode cur) {
        if (cur == null) return;
        searchBST(cur.left);
        if (pre == null) {
            count = 1;
        } else if (pre.val == cur.val) {
            count++;
        } else if (pre.val != cur.val) {
            count = 1;
        }
        pre = cur;
        if (count == maxCount) {
            list.add(cur.val);
        } 

        if (count > maxCount) {
            maxCount = count;// 更新最大的频率
            list.clear(); // 清空列表,之前的元素失效
            list.add(cur.val);
        }
        searchBST(cur.right);
    }
}

迭代

使用栈模拟递归,单层处理逻辑与递归中相同,因此不需要改变

class Solution {

    // 记录前一个指针
    private TreeNode pre = null;

    // 计算出现次数
    private int count = 0;

    // 最大的出现频率
    private int maxCount = 0;

    private List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (pre == null) {
                    count = 1;
                } else if (pre.val == cur.val) {
                    count++;
                } else if (pre.val != cur.val) {
                    count = 1;
                }
                if (count == maxCount) {
                    list.add(cur.val);
                } 
                if (count > maxCount) {
                    maxCount = count;// 更新最大的频率
                    list.clear(); // 清空列表,之前的元素失效
                    list.add(cur.val);
                }
                pre = cur;
                cur = cur.right;
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

}

本文链接: http://www.dtmao.cc/news_show_350212.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?