문제

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

해결 방법

• Tree를 순회하며 level값을 같이 넘김
• Tree를 순회할 때, 각 level 별로 몇 개의 노드가 있는지와 모든 노드의 합을 구함
• 순회를 마친 후 각 level 별로 모든 노드의 합 / 노드의 개수를 List에 담아 return

코드

class Solution {
    static long[] levelSum;
    static int[] levelCnt;

    public List<Double> averageOfLevels(TreeNode root) {
        if (root == null) {
            return new ArrayList<Double>();
        }
        levelSum = new long[10001];
        levelCnt = new int[10001];

        check(root, 1);
        
        int idx = 1;
        List<Double> answer = new ArrayList<>();
        while(levelCnt[idx] != 0) {
            answer.add((double)levelSum[idx] / levelCnt[idx]);
            idx ++;
        }

        return answer;
    }

    private void check(TreeNode now, int level) {
        levelSum[level] += now.val;
        levelCnt[level] ++;

        if (now.left != null) check(now.left, level +1);
        if (now.right != null) check(now.right, level + 1);
    }
}

결과