leetcode刷题：二叉树23（二叉搜索树中的众数）

501.二叉搜索树中的众数

力扣题目链接

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

假定 BST 有如下定义：

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

例如：

给定 BST [1,null,2,2],

返回[2].

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

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

两种思路：

1: 通用写法，哈希表，遍历树，把结果集存到hashmap，遍历频率value获取最大值，再遍历一遍获取结果集，处理成数组。

 HashMap<Integer, Integer> result = new HashMap<Integer, Integer>();

    public int[] findMode(TreeNode root) {
    
        //本题可以使用哈希表做
        traversal(root);
        Set<Integer> keys = result.keySet();
        int max = -1;
        for (Integer key : keys) {
    
            if (result.get(key) > max) {
    
                max = result.get(key);
            }
        }
        Set<Integer> resultSet = new HashSet<Integer>();
        for (Integer key : keys) {
    
            if (result.get(key) == max) {
    
                resultSet.add(key);
            }
        }
        int[] resultArr = new int[resultSet.size()];
        int index = 0;
        for (Integer key : resultSet) {
    
            resultArr[index] = key;
            index++;
        }
        return resultArr;
    }

    public void traversal(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        traversal(root.left);
        if (result.containsKey(root.val)) {
    
            result.put(root.val, result.get(root.val) + 1);
        } else {
    
            result.put(root.val, 1);
        }
        traversal(root.right);
    }

2.二叉搜索树写法：因为是二叉搜索树，非递减，所以一样的数肯定都是在一块的，计算每个数出现的次数，给一个最大出现次数，如果当前数出现次数比最大出现次数小，不做改变，若相等，则把当前数添加到结果集，如果比最大出现次数大，则清空结果集，当前数添加到结果集。

  List<Integer> list = new ArrayList<>();
    TreeNode parent;
    int maxTimes = 0;
    int curTimes = 0;

    public void inorderTraversal(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        inorderTraversal(root.left);
        if (root.val == parent.val) {
    
            curTimes++;
            //如果当前元素出现次数比最大次数大，则新的众数出现，原来的不是众数了
            if (curTimes > maxTimes) {
    
                maxTimes = curTimes;
                list.clear();
                list.add(root.val);
            } else if (curTimes == maxTimes) {
    
                //如果当前元素出现次数和最大次数相等，则新的众数出现
                list.add(root.val);
            }
        } else {
    
            curTimes = 1;
                      if (curTimes > maxTimes) {
    
                maxTimes = curTimes;
                list.clear();
                list.add(root.val);
            } else if (curTimes == maxTimes) {
    
                //如果当前元素出现次数和最大次数相等，则新的众数出现
                list.add(root.val);
            }
            parent = root;
        }
        inorderTraversal(root.right);
    }


    public int[] findMode(TreeNode root) {
    
        parent = root;
        inorderTraversal(root);
        int index = 0;
        int[] resultArr = new int[list.size()];
        for (Integer result : list) {
    
            resultArr[index] = result;
            index++;
        }
        return resultArr;
    }