LeetCode刷题【501】二叉搜索树中的众数

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

假定 BST 有如下定义：

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

例如：
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2

返回[2].

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

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

题解

根据题意，这棵BST树如果按照中序遍历的结果大概应该是这样的

[1,1,1,2,3,3,3,5,5,5,5,5,6,7]

这样再来看这道题的话是不是就看起来很好处理了。把原本数组遍历for循环的方法替换成中序遍历dfs方法，剩下的就是当前位置和前一位置比较，统计数量，和最长序列的数量对比。

如果和最长序列的长度相同，则加入结果集res中。

如果比最长序列的长度还长，则更新当前长度为最长序列，并把结果集res清空，再将当前值加入结果集中。

import java.util.ArrayList;
import java.util.List;

/**
 * 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 {

    private final List<Integer> list = new ArrayList<>();
    private Integer lastNum;
    private int maxCount = 0;
    private int currentCount;
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void dfs(TreeNode root){
        if (root==null)return;
        dfs(root.left);
        countNum(root.val);
        dfs(root.right);
    }

    private void countNum(Integer rootNum){
        if (!rootNum.equals(lastNum)){
            lastNum = rootNum;
            currentCount = 1;
        }else{
            currentCount++;
        }
        if (currentCount > maxCount){
            maxCount = currentCount;
            list.clear();
            list.add(rootNum);
        }else if (currentCount == maxCount){
            list.add(rootNum);
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)