Programming

Leetcode-637. Average of Levels in Binary Tree

Leetcode-637. Average of Levels in Binary Tree

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:

image

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:

image

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

<解題>

  • .offer(root) 是將元素添加到隊列的操作,用於初始化遍歷二叉樹的起始節點。
  1. 先用Queue把root加入,以及一個ArrayList存之後要回傳的陣列
  2. 當queue.size()>0,跑迴圈去計算每列的sum,若當前節點的左右節點非為空,則將它們加入queue中
  3. 計算每列平均

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>(List.of(root));
        //queue.offer(root);

        while(queue.size()>0){
            double size = queue.size(),level_sum = 0;
            for(int i =0 ; i<size;i++){
                TreeNode current = queue.poll();
                level_sum += current.val;
                if(current.left != null) queue.offer(current.left);
                if(current.right != null) queue.offer(current.right);
            }
            double level_avg = level_sum/ size;
            result.add(level_avg);
        }
        return result;
    }
}
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
可以寫成:
    Queue<TreeNode> q = new LinkedList<>(List.of(root));