leetcode501. 二叉搜索树中的众数

leetcode501. 二叉搜索树中的众数

三月 14, 2020

leetcode501. 二叉搜索树中的众数

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

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],

1
\
 2
/
2

返回[2].

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

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

关键点:二叉搜索树的中序遍历是一个递增的数组

问题转化成:求递增数组里面的众数
用一个nownum记录当前查的数是谁,max是之前的众数的出现次数,count是本次数出现的次数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int max=0,count=0;
    public int nownum=0;
    public ArrayList<Integer>list=new ArrayList<>();
    public int[] findMode(TreeNode root) {
        if(root==null)return new int[0];
        traverse(root);
        int[]ans=new int[list.size()];
        for(int i=0;i<list.size();i++)
            ans[i]=list.get(i);
        return ans;

    }
    public void traverse(TreeNode root){
        if(root==null)return;
        traverse(root.left);
        if(root.val==nownum){//当前还在计数
            count++;
            if(count>max){
            //更新list,当前的数才是众数
                max=count;
                nownum=root.val;
                list=new ArrayList<Integer>();
                list.add(root.val);
            }else if(count==max){
            //众数可能有多个
                list.add(root.val);
                nownum=root.val;
            }
            //小于的时候什么也干不了,所以只能nownum=root.val
            nownum=root.val;
        }else{
        //不是原来的数了,出现了一个新数
            nownum=root.val;
            count=1;
            if(count>max){//max可能是0,也就是刚开始
                max=count;
                list=new ArrayList<Integer>();
                list.add(root.val);
            }else if(count==max){
                list.add(root.val);
            }
        }
        traverse(root.right);
    }
}

leetcode 52/100