[3주차] 637. Average of Levels in Binary Tree

https://leetcode.com/problems/average-of-levels-in-binary-tree/?envType=study-plan-v2&envId=top-interview-150 

Average of Levels in Binary Tree - LeetCode

---

📝 문제

리진트리의 루트가 주어진다.  해당 트리의 각  레벨별 평균을 구해 리스트에 담아 리턴하시오.

단, 각 평균값은 소숫점 5번째 자리까지만 나타내어라.

 

🎈 풀이

https://foxtrot.tistory.com/32

[3주차] 199. Binary Tree Right Side View

 

이 문제에서 내가 비효율적으로 푼 방식을 조금 변형시켜 여기에 사용하면 좋을 것 같았다.

레벨별로 큐를 제어하는 방식이다.

 

시간복잡도: O(n)

공간복잡도: O(n)

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        ArrayList<Double> res = new ArrayList<Double>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Queue<TreeNode> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                temp.offer(queue.poll());
            }

            double size = temp.size();
            long sum = 0;
 
            while (!temp.isEmpty()) {
                TreeNode parent = temp.poll();
                sum += parent.val;
                if (parent.right != null) queue.add(parent.right);
                if (parent.left != null) queue.add(parent.left);
            }
            
            res.add(Math.floor(sum / size * 100000) / 100000.0);
        }

        return res;
    }
}

• 9~11행: 현재 queue 에 담겨있는 노드를 temp에 전부 옮긴다.
• 18행: temp 에서 값을 하나씩 뺀 후, sum에 더해 총합을 구한다. 자식은 다시 큐에 넣는다.
• temp 가 빈 상태면 해당 레벨순회가 끝난것을 의미하므로 평균을 구해서 결과 List에 넣는다.

 

주의할 점은 노드의 값 범위가 int 형 범위와 동일하기 때문에 더하는 과정에서 오버플로우가 일어날 수 있다. 따라서 sum 변수는 long으로 선언해야 한다.

 

 

📈 타 솔루션 참고

시간복잡도: O(n)

공간복잡도: O(n)

class Solution {
    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; 
    }
}

메모리를 줄이는 아주 간단한 방법이 있었다...

방식은 동일하나 temp를 사용하지 않아 내 코드보다 메모리를 덜 먹고, 의미없는 루프를 돌지 않아 시간도 적게 쓴다.

단지 10행에서 현재 Queue의 사이즈만 기록해 두면 해당 사이즈만큼의 노드가 동일 레벨에 존재함을 의미하게 된다.

이후 자식노드를 Queue에 넣어도, size만큼만 반복하기 때문에 다른 레벨을 침범하지 못하게 된다.