[LeetCode/Top Interview 150] [Binary Tree BFS (Breadth-First Search)] 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
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

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]

Constraints:

The number of nodes in the tree is in the range [1, 104].
-2^31 <= Node.val <= 2^31 - 1

전략:

BFS로 각 높이별로 순회하며 모든 값을 합산 후 해당 높이의 요소의 수만큼으로 나눠서 정답 리스트에 add한다.

코드 구현:

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> answer = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        Double sum = 0.0;
        int cnt = 1; // root
        int level_cnt = 1; // root

        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode now = q.poll();
            level_cnt--;
            
            sum += now.val;
            if (now.left!=null) {
                q.offer(now.left);
            }

            if (now.right!=null) {
                q.offer(now.right);
            }

            if (level_cnt==0) {
                answer.add(sum/cnt);
                sum = 0.0;
                cnt = level_cnt = q.size();
            }
        }

        return answer;
    }
}
Time: 3 ms (34.04%), Space: 44.3 MB (83.24%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0637-average-of-levels-in-binary-tree/0637-average-of-levels-in-binary-tree.java

Solutions 탭의 타인 코드:

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>(List.of(root));
        List<Double> ans = new ArrayList<>();
        while (q.size() > 0) {
            double qlen = q.size(), row = 0;
            for (int i = 0; i < qlen; i++) {
                TreeNode curr = q.poll();
                row += curr.val;
                if (curr.left != null) q.offer(curr.left);
                if (curr.right != null) q.offer(curr.right);
            }
            ans.add(row/qlen);
        }
        return ans;
    }
}
Time: 2 ms (97.19%), Space: 45.2 MB (6.96%) - LeetHub

회고:

이중 반복문을 너무 두려워 할 필요는 없지 않을까 싶다.