501. 二叉搜索树中的众数(Java) leecode_java语言求二叉树里面的众数

解题思路：

二叉搜索树，考虑中序遍历，此题类似有序遍历数组。

curCount 计算当前节点出现的次数，maxCount 计算众数出现最大次数。

返回结果是数组，所以要定义一个数组储存众数。

class Solution {
    //计算众数节点的值
    LinkedList<Integer> mode = new LinkedList<>();

    int curCount = 0, maxCount = 0;
    
    TreeNode prev = null;

    public int[] findMode(TreeNode root) {

        traverse(root);
		//最后返回的数组
        int[] res = new int[mode.size()];

        for (int i = 0; i < res.length; i++){

            res[i] = mode.get(i);

        }
        
       return res;


    }

    void traverse(TreeNode root){

        if(root == null){
            return;
        }
		
		//中序遍历
        traverse(root.left);

        if(prev == null ){
        	//初始化
            curCount = 1;
            maxCount = 1;
            mode.add(root.val);

        }else{
			//节点重复
            if(prev.val == root.val){

                curCount++;
                //当前节点出现次数与最大出现次数相同，加入另外一个众数
                if(curCount == maxCount){

                    mode.add(root.val);
                    
				//当前节点出现次数大于最大出现次数 ，更新最大节点出现次数
                }else if(curCount > maxCount){

                    mode.clear();
                    maxCount = curCount;
                    mode.add(root.val);
                }
            }
			//节点不重复
            if(root.val != prev.val){

                curCount = 1;

                if(curCount == maxCount){
                    mode.add(root.val);
                }
            }
        }

        prev = root; //更新节点

        traverse(root.right);

    }
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75