문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

중복 요소가 있는 이진 탐색 트리(BST)의 루트가 주어졌을 때, 해당 트리에서 가장 자주 나타나는 요소(모드)를 모두 반환해라.

트리에 모드가 두 개 이상 있는 경우, 순서에 상관없이 모두 반환해라.

BST가 다음과 같이 정의된다고 가정한다.

• 노드의 왼쪽 서브트리는 해당 노드의 키보다 작거나 같은 키를 가진 노드들만 포함한다.
• 노드의 오른쪽 서브트리는 해당 노드의 키보다 크거나 같은 키를 가진 노드들만 포함한다.
• 왼쪽 소브트리와 오른쪽 서브트리 모두 이진 탐색 트리여야 한다.

Example

#1

Input: root = [1, null, 2, 2]
Output: [2]

#2
Input: root = [0]
Output: [0]

Constraints

• 트리의 노드 수는 [1, 104] 범위에 있다.
• -10^5 <= Node.val <= 10^5

Solved

/**
 * 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 {
    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> counts = new HashMap<>();
        List<Integer> modes = new ArrayList<>();
        int[] maxCount = {0};

        inorder(root, counts, maxCount, modes);

        int[] result = new int[modes.size()];

        for(int i = 0; i < modes.size(); i++){
            result[i] = modes.get(i);
        }

        return result;
    }

    private void inorder(TreeNode node, Map<Integer, Integer> counts, int[] maxCount, List<Integer> modes){
        if(node == null) return;

        inorder(node.left, counts, maxCount, modes);

        int count = counts.getOrDefault(node.val, 0) + 1;
        counts.put(node.val, count);

        if(count > maxCount[0]){
            maxCount[0] = count;
            modes.clear();
            modes.add(node.val);
        }else if(count == maxCount[0]){
            modes.add(node.val);
        }

        inorder(node.right, counts, maxCount, modes);
    }
}