leetcode 508. Most Frequent Subtree Sum

문제

https://leetcode.com/problems/most-frequent-subtree-sum/description/

Most Frequent Subtree Sum - LeetCode

가장 많은 Subtree Sum 빈도수 배열을 찾는 문제. SubtreeSum 이란 rootval + leftSum + rightSum 을 의미

 

풀이

풀이 알고리즘은 다음과 같다.

1. inorder traversal 로 트리를 순회한다.
2. 순회하면서 HashMap에다 출현한 숫자를 카운팅한다. 
3. HashMap을 순회하면서 max(출현횟수)를 구한다. 
4. HashMap을 재순회하면서 max(출현횟수)  value를 가진 key들을 list에 추가하고 정답을 리턴한다.

 

코드

자바

class Solution {
    HashMap<Integer, Integer> map;
    
    public int[] findFrequentTreeSum(TreeNode root) {

        map = new HashMap<>();
        helper(root);
        int max = 0;
        for(int x : map.keySet()){
            max = Math.max(map.get(x),max);
        }

        ArrayList<Integer> l = new ArrayList<>();

        for(int x : map.keySet()){
            if(map.get(x) == max)l.add(x);
        }
        return l.stream().mapToInt(x->x).toArray();

    }

    public int helper(TreeNode root){

        if(root == null)return 0;
        int leftNodeSum = helper(root.left);//left
        int rightNodeSum = helper(root.right);//right
        int num = leftNodeSum + rightNodeSum + root.val;//get value
        map.put(num, map.getOrDefault(num, 0)+1);
        return num;

    }
}