📒

[LeetCode Top 150] 05-4. Average of Levels in Binary Tree

상태

완료

수업

Algorithm Solving

주제

LeetCode Top Interview 150

4 more properties

참고

문제해설

NOTE

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

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

•

입력 값 ⇒ TreeNode

•

출력 값 ⇒ Tree의 각 레벨 노드 평균 값

문제 로직고민

NOTE

•

이전 문제에서 동일레벨에 대해 순환하는 방식인 BFS를 그대로 활용하면 된다.

◦

BFS를 활용해서 Queue의 크기와, 동일레벨 순회를 통해 평균값을 구한다.

작성코드

NOTE

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {

        List<Double> result = new ArrayList();
        if(root == null) return result;

        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            double sum = 0;

            for(int i =0; i<size; i++){
                TreeNode node = queue.poll();
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);

                sum += node.val;
            }

            result.add(sum/size);
        }
        return result;
        
    }
}
Java
복사

정답코드

NOTE

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        LinkedList<Double> res = new LinkedList<Double>();
        if(root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while(queue.size() != 0){
            int size = queue.size();
            double sum = 0;

            for(int i = 0; i < size; i++){
                TreeNode temp = queue.poll();
                sum += temp.val;
                if(temp.left != null) queue.add(temp.left);
                if(temp.right != null) queue.add(temp.right);
                
            }
            res.add(sum/ size);
        }
        System.gc();
        return res;


    }
}
Java
복사
메모리를 가장 적게 사용하는 코드

•

System.gc()이외에는 놀라울정도로 코드가 동일해서 참고만 했다.