[Vssue]0501.二叉搜索树中的众数.md

[youngyangyang04]

https://www.programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html

[Du1in9]

public class Solution {
    private List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        inorderTraversal(root);                 // 中序数组
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : list) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int maxCount = 0;                       // 众数个数
        for (int count : map.values()) {
            maxCount = Math.max(maxCount, count);
        }
        List<Integer> res = new ArrayList<>();  // 所有众数
        for (int num : map.keySet()) {
            if (map.get(num) == maxCount) {
                res.add(num);
            }
        }
        int[] result = new int[res.size()];     // 转换为 int[]
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}

[JIE-yx]

树的题套路比较固定，难怪都是简单题居多。但是简单的前提是，你得对树的理解比较深刻 class Solution {

private TreeNode pre;

private int maxCount ;

private int count;

/**
    存放maxCount次数对应的数字
*/
private Stack<Integer> stack = new Stack();

public int[] findMode(TreeNode root) {
    if (root.left == null && root.right == null) {
        int[] result = new int[1];
        result[0] = root.val;
        return result;
    }

    // 前序递归遍历
    find(root);
    int[] result = new int[stack.size()];
    int i = 0;
    while (!stack.isEmpty()) {
        result[i] = stack.pop();
        i++;
    }
    return result;
}

public void find(TreeNode node) {
    if (node == null) {
        return;
    }
    find(node.left);
    if (pre == null) {
        count = 1;
        maxCount = 1;
    } else if (pre.val == node.val) {
        count++;
    } else {
        count = 1;
    }       
    if (count == maxCount) {
        stack.push(node.val);
    } 
    if (count > maxCount) {
        maxCount = count;
        stack = new Stack();
        // while (!stack.isEmpty()) {
        //     stack.pop();
        // }
        stack.push(node.val);
    }
    pre = node;
    find(node.right);
}

}