[LeetCode] 501. Find Mode in Binary Search Tree

class Solution {
    public int[] findMode(TreeNode root) {
        List<Integer> values = new ArrayList();
        dfs(root, values);

        int maxStreak = 0;
        int currStreak = 0;
        int currNum = 0;
        List<Integer> ans = new ArrayList();

        for (int num : values) {
            if (num == currNum) {
                currStreak++;
            } else {
                currStreak = 1;
                currNum = num;
            }
            
            if (currStreak > maxStreak) {
                ans.clear();
                maxStreak = currStreak;
            }
            
            if (currStreak == maxStreak) {
                ans.add(num);
            }
        }
        
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        
        return result;
    }
    
    public void dfs(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }
        
        dfs(node.left, values);
        values.add(node.val);
        dfs(node.right, values);
    }
}

 

in-order traversal을 사용하여 오름차순으로 트리를 순회한다.

오름차순으로 정렬이 되어있는 상태이기 때문에 리스트를 순회하기 좀 더 편하다

 

오름차순으로 생성된 리스트를 돌면서

 

각 값들이 몇번이나 나타나는지 체크한다.

 

등장수가 적다면 넘어가고, 

등장수가 같다면 modes를 담아두는 리스트에 추가하고

등장수가 더 많다면 기존 modes 리스트를 지우고 해당 값을 추가한다.