/*
 * 演算法 / Algorithm: 廣度優先搜尋 (BFS)，使用 std::queue。
 * 每一層開始前用 q.size() 記下該層節點數，出佇列該麼多次、
 * 累加後算平均，把左右孩子推入佇列作為下一層。
 * BFS with std::queue: snapshot q.size() as the level size, dequeue that
 * many, sum and average, and push children as the next level.
 */

/**
 * Definition for a binary tree node. / 二元樹節點定義（LeetCode 已提供）。
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;             // 存放每層平均值的答案陣列 / holds each level's average
        if (root == nullptr) return res; // 保險：空樹回傳空陣列 / guard: empty tree → empty result

        // std::queue 是標準函式庫的佇列（先進先出）。
        // std::queue is the STL first-in-first-out container.
        queue<TreeNode*> q;
        q.push(root);                   // 把根節點放入佇列 / enqueue the root

        while (!q.empty()) {            // 佇列非空表示還有一層要處理 / non-empty ⇒ a level remains
            int levelSize = q.size();   // 凍結這一層的節點數 / snapshot this level's node count
            long long sum = 0;          // 64 位元整數累加，避免溢位 / 64-bit accumulator avoids overflow

            // 迴圈剛好跑 levelSize 次，處理完整一層。
            // Loop exactly levelSize times to cover the whole level.
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front(); // 讀取佇列最前面的節點 / peek the front node
                q.pop();                    // 把它移出佇列 / remove it from the queue
                sum += node->val;           // 累加節點值 / add the node's value

                // 有孩子就推入佇列，成為下一層。
                // Push any children to form the next level.
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }

            // static_cast<double> 讓除法變浮點除法，結果才有小數。
            // static_cast<double> forces floating-point division for a decimal result.
            res.push_back(static_cast<double>(sum) / levelSize);
        }

        return res;                     // 回傳所有層的平均 / return averages of all levels
    }
};