501. Find Mode in Binary Search Tree (해석 + 풀이)

의역: (BST) 자식이 부모와 같은 값을 가질 수 있는 조건이 추가된 이진트리가 주어질 때 해당 트리에서 가장 많이 나온 노드값 들의 배열을 반환하시오  

의역: 첫 번째 예시에서는 2가 가장 많은 노드 값이었기 때문에 2를 반환

두 번째 예시에서는 0이 가장 많은 노드 값이기 때문에 0을 반환

 

풀이:

1. 전위순회(dfs) + Map

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    // 가장 빈도가 높게 나온 횟 수
    private int maxValue=1;
    private HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    // 전위순회 알고리즘 (DFS)
    public void helper(TreeNode2 root){
    	// HashMap의 contains() 함수를 사용해도 되지만 더 효율적으로 바꾼 것
        if(root!=null){
            Integer value = map.get(root.val);

            if(value!=null){
            	// 최대 빈도 갱신
                if(value+1>maxValue)
                    maxValue = value+1;
                map.put(root.val,value+1);}

            else map.put(root.val,1);
            helper(root.right);
            helper(root.left);
        }
    }
    public int[] findMode(TreeNode2 root) {
        List<Integer> ans = new ArrayList<Integer>();
        helper(root);

        Set<Integer> set = map.keySet();
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()){
            int key = it.next();
            int value = map.get(key);
            // 가장 빈도가 높은 횟수랑 같다면 추가
            if(value==maxValue)
                ans.add(key);
        }
        return  ans.stream()
                .mapToInt(i -> i)
                .toArray();

    }
}

1-1 map을 사용하지 않고 BST의 성질을 이용해 개선 시킨 코드

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    ArrayList<Integer> ans;
    int maxCount;
    int count;
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        ans = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        helper(root);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    public void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root.left);

        int rootValue = root.val;
        // 루트 노드인 경우와 값이 달라진 경우
        if (pre == null || rootValue != pre.val) {
            count = 1;
        } else {
            count++;
        }
        // maxCount 최대 빈도 수와 비교 해서 크다면 ArrayList 최신화
        if (count > maxCount) {
            ans.clear();
            ans.add(rootValue);
            maxCount = count;
        } else if (count == maxCount) {
            ans.add(rootValue);
        }
        pre = root;

        helper(root.right);
    }
}

메모: BST 중복값을 허용하는 이진 트리

 

링크: https://leetcode.com/problems/find-mode-in-binary-search-tree/description/