[LeetCode] 637. Average of Levels in Binary Tree

https://leetcode.com/problems/average-of-levels-in-binary-tree

개요

1. 이진 트리의 root 노드가 주어진다.
   • 노드의 개수는 최소 한개
2. 동일 레벨 노드 사이의 평균값을 구하라.

문제 해결 아이디어

• 동일 레벨 노드 간의 값을 연산해야 한다.
• 서브 트리에서 이전 루트 노드가 저장되어야 다음 노드를 알아낼 수 있다.

🧐 Breath First Search 방식

의사 코드

1. 큐에 루트 노드를 삽입한다.
2. 큐의 사이즈를 구한다.
3. 큐에서 루트 노드를 삭제한다.
4. 루트 노드의 left 노드를 큐에 삽입한다.
5. 루트 노드의 right 노드를 큐에 삽입한다.
6. 루트 노드의 값을 사이즈와 연산해 평균값을 구한다.

while(큐가 비어있지 않음){
	int size = 큐 사이즈;
    double sum = 0;
    for(int i=0 부터 size까지){
    	TreeNode n = 큐.remove();
        sum += n.val;
        do 큐에 자식 노드 삽입;
    }
    avg = sum/size
}

결과

전체 코드 github 링크

다른 풀이

public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans=new ArrayList<>();
        if(root==null){
            return ans;
        }
       Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int n=q.size();
           double avg=0l;
            for(int i=0;i<n;i++){
                 TreeNode curr=q.poll();
                avg=avg+(double)curr.val;
                if(curr.left!=null){q.add(curr.left);}
                if(curr.right!=null){q.add(curr.right);}
            }
            avg=avg/n;
            ans.add(avg);
        }
       return ans; 
    }

특정 레벨의 모든 요소를 큐에 넣은 다음 그 평균을 계산한다.
솔루션을 살펴봤는데, 대부분 나와 동일하게 접근한 것 같다.
평소에 자료 구조를 활용하는 것이 조금 어려운 것 같다고 생각하고 있었는데, 다른 솔루션과 동일하게 큐를 가장 좋은 자료구조라고 생각하고 활용한 부분이 뿌듯하다.

이번 문제에서 생각보다 복병이었던 부분은 double 값의 연산이었다.

java는 double에서 소수점 이하 0들은 그냥 버림처리하기 때문에 문제의 조건인 [1.00000, 3.00000] 이런 식으로 패딩해서 표현하는 부분에서 서치를 많이했다.
그런데 역시나 java의 double은 이런 경우 소수점 조절이 불가한 것 같다.
이런 특성을 알았으면 조금 더 문제 풀이 시간을 줄일 수 있었을텐데 아쉽다.
java의 기본적인 부분에 대해서도 더 공부하는 계기가 될 것 같다.