[LeetCode] 637. Average of Levels in Binary Tree

Average of Levels in Binary Tree - LeetCode

이진 트리의 루트가 주어졌을 때, 각 레벨에 있는 노드의 평균값을 배열의 형태로 반환합니다.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2:

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

 

문제접근

트리를 탐색하면서 노드의 평균값을 구해야 합니다.

 

DFS와 BFS를 활용할 수 있습니다.

이번에는BFS를 활용해서 탐색해 보겠습니다.

 

결과를 보면 왼쪽의 값부터 탐색을 하는것을 알 수 있습니다.

따라서 left부터 q에 넣어줄 것입니다.

 

public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            int size = q.size();
            double sum = 0;				
            for(int i=0; i<size; i++) {
                TreeNode node = q.poll();
                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);

                sum += node.val;		
            }
            res.add(sum/size);			
        }
        return res;
    }

 

시간복잡도

트리를 전부 탐색하고 있습니다.

O(n)의 시간복잡도기 필요합니다.

 

다른사람의 풀이

DFS로 해결한 방벙입니다.

개인적으로 BFS보다 이해하기 어려운것 같습니다.

 

하지만 트리를 전부 탐색한다는 관점에서 이해하려고 하면 금방 이해될것입니다.

class Solution {
    
    List<double[]> store = new ArrayList<>(); // it will store sum, no. of nodes at each level
    public List<Double> averageOfLevels(TreeNode root) {
        
        List<Double> res = new ArrayList<>();
        traverse(root, 0);
        for(double[] cur: store){
            res.add(cur[0]/cur[1]);
        }
        return res;
    }
    
    private void traverse(TreeNode node, int level){
        
        if(node == null) return;
        
        if(store.size() <= level) store.add(new double[2]);
        
        // update sum and no. of nodes at curlevel
        store.get(level)[0] += node.val;
        store.get(level)[1]++;
        
        traverse(node.left, level+1);
        traverse(node.right, level+1);
    }
}

 

느낀점

트리 문제는 보통 트리를 탐색하는것에서 벗어나지 않는것 같습니다.

DFS, BFS를 둘다 잘 활용해서 푸는 연습을 해야겠습니다.  

 

참고

JAVA || BOTH DFS & BFS SOLUTION WITH TC & SC - Average of Levels in Binary Tree - LeetCode