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

1 问题

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按任意顺序返回。

假定 BST 满足如下定义：

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

示例 1

输入：root = [1,null,2,2]
输出：[2]

示例 2

输入：root = [0]
输出：[0]

提示

• 树中节点的数目在范围 [1, $10^4$] 内
• $-10^5$ <= Node.val <= $10^5$

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

2 解题思路

2.1 前序遍历（DFS）

利用前序遍历，统计每个数字的频率，保存于一个map中，并记录全局频次最大值，遍历完毕，将map中频次等于频次最大值的数值输出。

详见代码中方法：findMode2()。

2.2 中序遍历

• 全局记录当前节点的前一节点prev，全局频次最大值max，当前节点值的频次currentCnt，结果集res；
• 先统计左子树，对于没有prev的节点，初始化prev=1,max=1，并临时保存当前节点值；
• 若左子树统计完毕，当前值等于prev.val，则currentCnt++，意思是出现相同数值，若此时max==currentCnt，res.add(当前值)；若max<currentCnt，则清空res，更新max；
• 若当前值不等于prev.val，则重置currentCnt=1。

  详见代码中方法：findMode()。

3 代码

/**
 * 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 {
    Map<Integer, Integer> valueFreqMap;
    int max = Integer.MIN_VALUE;

    public int[] findMode2(TreeNode root) {
        if (null == root.left && null == root.right) {
            return new int[]{root.val};
        }
        valueFreqMap = new HashMap();
        preorderTraversal(root);
        List<Integer> res = new ArrayList();
        for (Integer e : valueFreqMap.keySet()) {
            if (max == valueFreqMap.get(e)) {
                res.add(e);
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private void preorderTraversal(TreeNode root) {
        if (null == root) {
            return;
        }
        int m = valueFreqMap.getOrDefault(root.val, 0);
        valueFreqMap.put(root.val, ++m);
        if (max < m) {
            max = m;
        }
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    //inorder traversal
    List<Integer> res = new ArrayList();
    TreeNode prev = null;
    // 当前元素的重复次数
    int currentCnt = 0;

    public int[] findMode(TreeNode root) {
        inorderTraversal(root);
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private void inorderTraversal(TreeNode root) {
        if (null == root) {
            return;
        }
        inorderTraversal(root.left);
        if (null == prev) {
            currentCnt = 1;
            max = 1;
            res.add(root.val);
        } else {
            //repeated num
            if (root.val == prev.val) {
                currentCnt++;
                if (currentCnt == max) {
                    res.add(root.val);
                } else if (currentCnt > max) {
                    //update the max frequent num
                    res.clear();
                    max = currentCnt;
                    res.add(root.val);
                }
            } else {
                // no repeated num happened
                currentCnt = 1;
                if (currentCnt == max) {
                    res.add(root.val);
                }
            }
        }

        prev = root;
        inorderTraversal(root.right);
    }
}