力扣501. 二叉搜索树中的众数

思路1：暴力法，把所有内容遍历入map中，然后map转list，按照出现的次数排序，for循环 获取排序值和第一个相同的数字。

思路2：利用二叉排序树的原理，中序遍历能让数组是有序的，左中右去遍历，可以第一次遍历，获取最大次数，第二次遍历存储与最大次数相同的数字；
优化思路2：用双指针法只需遍历一次，把原本的假最大值入数组的内容先删除，再入新的最大值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int curCount = 0; //当前数字出现次数
    int maxCount = 0; //整个数组中出现的最大次数
    ArrayList<Integer> list = new ArrayList();
    TreeNode pre = null;

    public int[] findMode(TreeNode root) {
        //中序遍历会是有序的，左中右
        findMode1(root);
        //转换List
        int [] result = new int [list.size()];
        for(int i = 0; i<list.size();i++){
            result[i] = list.get(i);
        }
        return result;
    }

    public void findMode1(TreeNode root) {
        if(root==null) return;
        //1、左
        findMode1(root.left);

        //2、中，主要的处理逻辑
        //记录当前数字出现的次数，如果pre是null,root是第一个值，次数为1；遇到前后两个值不等，归1
        if(pre == null || pre.val != root.val) {
            curCount = 1;
        }else {//前后两个值相等，次数+1
            curCount++;
        }
        //如果当前数字出现次数更大，说明以前list记录的无效，先删除，再加新的最大值
        if(curCount > maxCount) {
            list.clear();
            maxCount = curCount;
            list.add(root.val);
        }else if (curCount == maxCount){
            list.add(root.val);
        }
        //把当前的root赋值给pre, pre一直跟在root后面
        pre = root;

        //3、右
        findMode1(root.right);

        return;  

    }

}
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