501. 二叉搜索树中的众数_树的众数

一、题目描述

二、解题

中序遍历

这题先使用中序遍历，将数据变成有序的，然后查找众数，这题的区别众数可以是多个，与之前的169题不一样的是这个题的众数的数量是大于N/2的，可以使用摩尔投票法。所以这题也提供了一个思路如何在数组中查找众数。

class Solution {
    List<Integer> answer = new ArrayList<Integer>();
    int base, count, maxCount;
    public int[] findMode(TreeNode root) {
       //这里不需要使用哈希表 很占空间
       dfs(root);
       //对一个列表进行查找，找一个众数
       int[] res = new int[answer.size()];
       for(int i = 0;i<answer.size();i++){
           res[i] = answer.get(i);
       }
       return res;
    }
    // 中序遍历
     public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        update(root.val);
        dfs(root.right);
    }
    //更新数据
    public void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.add(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer.clear();
            answer.add(base);
        }
    }
}
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