637 : Average of Levels in Binary Tree ( leetcode / java )

 

*해결 과정

 

각 depth 별로 list를 만들고 저장하는 방법이 있고,

BFS로 같은 level을 순회하면서 값을 계산하는 방법이 있다.

 

1. List<List<Integer>> 이용

2. LinkedList를 통해 BFS를 이용

 

*1번 방법

class Solution {
    
    List<List<Integer>> list = new ArrayList<>();
    
    public List<Double> averageOfLevels(TreeNode root) {
        if(root==null) return null;
        DFS(root,0);
        
        List<Double> doubleList = new ArrayList<>();
        for(List<Integer> integerList : list){
            int size = integerList.size();
            double sum=0;
            for(int val : integerList ){
                sum+=val;
            }
            doubleList.add(sum/size);
        }
        return doubleList;
    }
    
    public void DFS(TreeNode root, int depth){
        if(list.size()==0 || list.size()<=depth){
            List<Integer> newList = new ArrayList<>();
            newList.add(root.val);
            list.add(newList);
        } else
            list.get(depth).add(root.val);
        

        if(root.left!=null) DFS(root.left,depth+1);
        if(root.right!=null) DFS(root.right,depth+1);
    }
}

 

*결과

 

중요한 것은 List 내부에 list를 만들 때, null인지 아닌지 확인하고 새로 arrayList를 만들어야 한다. 따라서 depth를 통해 list.size()<=depth로 null 유무를 확인한다.

 

만약 list의 size가 2인데 list.get(2)는 IndexOutofBoundsException 오류가 발생하므로 if(list.get(depth)=null)는 사용할 수 없다. 따라서 (list.size() <= depth)로 확인한다. 

 

이후 각 List를 순회하면서 값을 구한다.

 

*2번 방법  

class Solution {
    
    List<Double> list = new ArrayList<>();
    
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int divideSize = size;
            double sum = 0;
            while( --size >= 0){
                TreeNode tree = queue.poll();
                sum += tree.val;
                if(tree.left !=null) queue.add(tree.left);
                if(tree.right !=null) queue.add(tree.right);
            }
            list.add(sum/divideSize);
        }
        return list;
    }
}

*결과

 

LinkedList를 통해 bfs로 해결이 가능하다. 처음 root를 추가하고, 이후에 추가되는 queue의 갯수에 따라서 size가 정해진다. 다시 while문을 내부에 돌려 size만큼 있는 val들을 더해주고 size로 나눠준다.