501.二叉搜索树中的众数

题目描述

题解

哈希表

直观上能想到的方法就是遍历整个BST, 然后用哈希表记录每个值出现的次数.

然后在遍历哈希表, 将出现次数最多的数放进数组中返回即可

class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();

    public int[] findMode(TreeNode root) {
        dfs(root);

        List<Integer> resList = new ArrayList<>();

        int max = 0;
        Set<Integer> keySet = map.keySet();
        for (int key : keySet) {
            max = Math.max(max, map.get(key));
        }

        for (int key : keySet) {
            if (map.get(key) == max) {
                resList.add(key);
            }
        }

        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }

        return res;
    }

    private void dfs(TreeNode root) {
        if (root != null) {
            map.put(root.val, map.getOrDefault(root.val, 0) + 1);
            dfs(root.left);
            dfs(root.right);
        }
    }
}

中序遍历(推荐)

利用BST中序遍历结果是升序的性质, 对给定的树进行中序遍历, 那么重复出现的数将排列在一起.

要经过两次中序遍历, 第一次中序遍历得到次数最多的元素有几个, 然后创建相应容量的数组用于存放结果.

第二次中序遍历就是把符合要求的数值保存下来

public class lc501 {
    private TreeNode pre = null;
    private int[] ret;
    private int retCount = 0;
    private int maxCount = 0;
    private int currCount = 0;

    public int[] findMode(TreeNode root) {
        inOrder(root);
        pre = null;
        ret = new int[retCount];
        retCount = 0;
        currCount = 0;
        inOrder(root);
        return ret;
    }

    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        if (pre != null && pre.val == root.val) {
            currCount++;
        } else {
            currCount = 1;
        }
        if (currCount > maxCount) {
            maxCount = currCount;
            retCount = 1;
        } else if (currCount == maxCount) {
            if (ret != null) {
                ret[retCount] = root.val;
            }
            retCount++;
        }
        pre = root;
        inOrder(root.right);
    }
}