[BFS] Average of Levels in Binary Tree

이진 트리의 수준 평균

Average of Levels in Binary Tree - LeetCode

root이진 트리의 경우 각 수준의 노드 평균 값을 배열 형식으로 반환합니다 . 실제 답변 이내의 답변만 인정됩니다. 10-5

 

예시 1:

입력: 루트 = [3,9,20,null,null,15,7]
 출력: [3.00000,14.50000,11.00000]
설명: 레벨 0 노드의 평균값은 3, 레벨 1 노드의 평균값은 14.5, 레벨 2 노드의 평균값은 11입니다.
따라서 [3, ​​14.5, 11]을 반환합니다.

예 2:

입력: 루트 = [3,9,20,15,7]
 출력: [3.00000,14.50000,11.00000]

 

제약:

• 트리의 노드 수가 범위 내에 있습니다 .[1, 10^4]
• -2^31 <= Node.val <= 2^31 - 1

---

문제풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        LinkedList<Double> list = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>(); 

        if (root == null) {
            return list;
        }
        q.add(root);
        while (!q.isEmpty()) {
            int n = q.size(); 
            double sum = 0.0;
            for (int i = 0; i < n; i++) {
                TreeNode node = q.poll(); 
                sum += node.val; 
                if (node.left != null) { 
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            list.add(sum / n); 
        }
        return list;
    }


}

 

노드를 트리의 레벨 순으로 값을 저장하고 그 값의 평균을 list로 반환하기로 하였다. 

각 node 데이터를 레벨별로 순회하여 list.add(sum/n)으로 평균을 구하여 반환하였다.