[Java][Leetcode][BST] 501. Find Mode in Binary Search Tree

문제  : 

예시 :

제한 조건 :

 

WAY 1: 

BST방문해서 모든 수/카운트 횟수를 MAP에 저장하고, 후에 그 MAP에 있는 데이터 기반으로 최대 횟수 숫자 뽑으면 되겠다.

생각함

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

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

        int maxCount = 0;
        ArrayList<Integer> resultArray = new ArrayList<>();

        for(int key: map.keySet()) {
            if(maxCount < map.get(key)) {
                maxCount = map.get(key);
                resultArray.clear();
                resultArray.add(key);
            } else if(maxCount == map.get(key)) {
                resultArray.add(key);
            }
        }

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

    private void checkTree(TreeNode node) {
        if(node == null) return;

        int count = map.get(node.val) == null ? 0 : map.get(node.val);
        map.put(node.val, ++count);

        checkTree(node.left);
        checkTree(node.right);
    }
}

그렇게 나온 솔루션!

 

한 번의 시도만에 성공!

Time complexity : O(n)
-> findMode method 의 map.keySet : O(n)
     checkTree method : O(n)
Space Complexity : O(n)
-> map : O(n)

 

하지만 결과가 맘에 들지 않았음.

 

계속 더 생각을 해보니까..

 

WAY2 :

check하는 곳에서 해보면 안될까 ? 생각이 들었다.

class Solution {
    List<Integer> values = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        checkNode(root, Long.MAX_VALUE, 0, 0);
        
        int[] result = new int[values.size()];
        for(int i=0; i<values.size(); i++) {
            result[i] = values.get(i);
        }
        return result;
    }

    private void checkNode(TreeNode node, long parentValue, int count, int maxCount) {
        if(node == null) return;

        if(node.val == parentValue) {
            count++;
        } else {
            count = 1;
        }

        if(count > maxCount) {
            maxCount = count;
            values.clear();
            values.add(node.val);
        } else if(count == maxCount) {
            values.add(node.val);
        }

        checkNode(node.left, node.val, count, maxCount);
        checkNode(node.right, node.val, count, maxCount);
    }
}

그래서 이렇게 했는데, 될 것 같으면서도 안되는것이 아주 어려웠다.

역시 리커젼은 내가 너무너문머ㅜㄴ머ㅜ 어려워하는 부분..

 

WAY 3:

그래서 유튜브의 도움을 받았따

 

https://youtu.be/1FJDyBSfEbo?si=pbfoLt20nMPbXBKx

 

근데! 내가 놓친 부분은 바로바로

sorted array 이기 때문에 inorder 방식으로 찾으면 되는 것!

inorder 방식은 왼쪽 -> 나자신 -> 오른쪽 이렇게 확인해보면 되는 것!

 

그래서 나온 코드 :

class Solution {
    List<Integer> values = new ArrayList<>();
    int count, parentValue=0, maxCount;
    public int[] findMode(TreeNode root) {
        checkNode(root);
        
        int[] result = new int[values.size()];
        for(int i=0; i<values.size(); i++) {
            result[i] = values.get(i);
        }
        return result;
    }

    private void checkNode(TreeNode node) {
        if(node == null) return;

        checkNode(node.left);

        if(node.val == parentValue) {
            count++;
        } else {
            count = 1;
        }

        if(count > maxCount) {
            maxCount = count;
            values.clear();
            values.add(node.val);
        } else if(count == maxCount) {
            values.add(node.val);
        }

        parentValue = node.val;
        checkNode(node.right);
    }
}

 

따단!

Time complexity : O(n)
Space Complexity : O(n)