LeetCode-501

题目

结果

代码

标准版

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

    public int[] findMode(TreeNode root) {
        dfs(root);
        int max = Integer.MIN_VALUE;
        for (int key : map.keySet()) {
            max = Math.max(max, map.get(key));
        }
        List<Integer> keys = new ArrayList<>();
        for (int key : map.keySet()) {
            if (map.get(key) == max) {
                keys.add(key);
            }
        }
        int[] ans = new int[keys.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = keys.get(i);
        }
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        if (map.containsKey(root.val)) {
            map.put(root.val, map.get(root.val) + 1);
        } else {
            map.put(root.val, 1);
        }
        dfs(root.left);
        dfs(root.right);
    }
}

进阶版

class Solution {
    private int maxNum = Integer.MIN_VALUE;
    private int currentNum = Integer.MIN_VALUE;
    private int count = 0;
    private final List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        // 计算众数出现的次数
        dfs1(root);
        // 重置
        currentNum = Integer.MIN_VALUE;
        count = 0;
        // 根据已经求得的众数出现的次数判断是否为众数
        dfs2(root);
        // 把list转为int[]
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    
    // 计算众数出现的次数
    private void dfs1(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs1(root.left);
        if (currentNum == Integer.MIN_VALUE) {
            currentNum = root.val;
            count++;
            maxNum = Math.max(maxNum, count);
        } else if (currentNum != root.val) {
            currentNum = root.val;
            count = 1;
            maxNum = Math.max(maxNum, count);
        } else {
            count++;
            maxNum = Math.max(maxNum, count);
        }
        dfs1(root.right);
    }

    // 根据已经求得的众数出现的次数判断是否为众数
    private void dfs2(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs2(root.left);
        if (currentNum == Integer.MIN_VALUE) {
            currentNum = root.val;
            count++;
        } else if (currentNum != root.val) {
            currentNum = root.val;
            count = 1;
        } else {
            count++;
        }
        if (count == maxNum) {
            list.add(currentNum);
        }
        dfs2(root.right);
    }
}

复杂度

时间复杂度：O（n），n为节点个数

空间复杂度：O（1），递归的栈开销不考虑在内。