Average of Levels in Binary Tree

This approach uses Breadth-First Search (BFS), which naturally processes the tree level by level. We use a queue to keep track of nodes to visit. For each level, we iterate through all nodes on that level, calculate their sum and count, then compute the average and add it to our result list. This is a very intuitive and direct way to solve the problem.

1. If root is null, return an empty list.
2. Initialize a result list averages and a Queue with the root node.
3. Loop while the queue is not empty: a. Get the current size of the queue, levelSize. b. Initialize levelSum = 0.0. c. Loop levelSize times: i. Dequeue a node. ii. Add node.val to levelSum. iii. Enqueue node.left if it's not null. iv. Enqueue node.right if it's not null. d. Calculate the average levelSum / levelSize and add it to averages.
4. Return averages.

BFS is an iterative algorithm that is perfectly suited for problems requiring level-by-level processing. The algorithm proceeds as follows:

1. Create a list averages to store the result. If the root is null, return an empty list.
2. Initialize a Queue (e.g., a LinkedList) and add the root node to it.
3. Enter a loop that continues as long as the queue is not empty. This loop processes one level of the tree in each iteration.
4. Inside the loop, first, get the number of nodes currently in the queue. This value, levelSize, represents the number of nodes at the current level.
5. Initialize a variable levelSum to 0.0 to accumulate the sum of node values for the current level.
6. Start an inner loop that runs levelSize times. In this loop, we process each node of the current level.
7. Dequeue a node, add its value to levelSum, and enqueue its non-null children (left and right).
8. After the inner loop finishes, all nodes for the current level have been processed. Calculate the average for the level (levelSum / levelSize) and add it to the averages list.
9. The outer loop then continues to the next level. Once the queue is empty, all levels have been processed, and the averages list contains the final result.

/**
 * 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;
 *     }
 * }
 */
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<>();
        if (root == null) {
            return averages;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            double levelSum = 0.0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                levelSum += currentNode.val;
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            averages.add(levelSum / levelSize);
        }

        return averages;
    }
}