当前位置:网站首页>leetcode刷题:二叉树23(二叉搜索树中的众数)

leetcode刷题:二叉树23(二叉搜索树中的众数)

2022-07-07 10:30:00 涛涛英语学不进去

501.二叉搜索树中的众数

力扣题目链接

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

假定 BST 有如下定义:

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

例如:

给定 BST [1,null,2,2],

501. 二叉搜索树中的众数

返回[2].

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

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

两种思路:

1: 通用写法,哈希表,遍历树,把结果集存到hashmap,遍历频率value获取最大值,再遍历一遍获取结果集,处理成数组。

 HashMap<Integer, Integer> result = new HashMap<Integer, Integer>();

    public int[] findMode(TreeNode root) {
    
        //本题可以使用哈希表做
        traversal(root);
        Set<Integer> keys = result.keySet();
        int max = -1;
        for (Integer key : keys) {
    
            if (result.get(key) > max) {
    
                max = result.get(key);
            }
        }
        Set<Integer> resultSet = new HashSet<Integer>();
        for (Integer key : keys) {
    
            if (result.get(key) == max) {
    
                resultSet.add(key);
            }
        }
        int[] resultArr = new int[resultSet.size()];
        int index = 0;
        for (Integer key : resultSet) {
    
            resultArr[index] = key;
            index++;
        }
        return resultArr;
    }

    public void traversal(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        traversal(root.left);
        if (result.containsKey(root.val)) {
    
            result.put(root.val, result.get(root.val) + 1);
        } else {
    
            result.put(root.val, 1);
        }
        traversal(root.right);
    }

在这里插入图片描述

2.二叉搜索树写法:因为是二叉搜索树,非递减,所以一样的数肯定都是在一块的,计算每个数出现的次数,给一个最大出现次数,如果当前数出现次数比最大出现次数小,不做改变,若相等,则把当前数添加到结果集,如果比最大出现次数大,则清空结果集,当前数添加到结果集。

  List<Integer> list = new ArrayList<>();
    TreeNode parent;
    int maxTimes = 0;
    int curTimes = 0;

    public void inorderTraversal(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        inorderTraversal(root.left);
        if (root.val == parent.val) {
    
            curTimes++;
            //如果当前元素出现次数比最大次数大,则新的众数出现,原来的不是众数了
            if (curTimes > maxTimes) {
    
                maxTimes = curTimes;
                list.clear();
                list.add(root.val);
            } else if (curTimes == maxTimes) {
    
                //如果当前元素出现次数和最大次数相等,则新的众数出现
                list.add(root.val);
            }
        } else {
    
            curTimes = 1;
                      if (curTimes > maxTimes) {
    
                maxTimes = curTimes;
                list.clear();
                list.add(root.val);
            } else if (curTimes == maxTimes) {
    
                //如果当前元素出现次数和最大次数相等,则新的众数出现
                list.add(root.val);
            }
            parent = root;
        }
        inorderTraversal(root.right);
    }


    public int[] findMode(TreeNode root) {
    
        parent = root;
        inorderTraversal(root);
        int index = 0;
        int[] resultArr = new int[list.size()];
        for (Integer result : list) {
    
            resultArr[index] = result;
            index++;
        }
        return resultArr;
    }

在这里插入图片描述

原网站

版权声明
本文为[涛涛英语学不进去]所创,转载请带上原文链接,感谢
https://blog.csdn.net/niTaoTaoa/article/details/125633896