/*
 * 演算法 / Algorithm: 廣度優先搜尋 (BFS)。用一個陣列當作佇列，
 * 一層一層走訪。每一層開始前先記下該層的節點數 (levelSize)，
 * 剛好做那麼多次出佇列，累加值後算平均。
 * BFS with an array-based queue: process level by level; snapshot the
 * level's node count, dequeue exactly that many, sum them, store the average.
 */

/**
 * Definition for a binary tree node. / 二元樹節點的定義（LeetCode 已提供）。
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 回傳一個 double 陣列；*returnSize 用來告訴呼叫者陣列長度。
// Return a double array; *returnSize tells the caller how long it is.
double* averageOfLevels(struct TreeNode* root, int* returnSize) {
    // 最多 10^4 個節點，樹的層數也不會超過 10^4，先開夠大的空間。
    // At most 10^4 nodes, so at most 10^4 levels; allocate enough room.
    double* res = (double*)malloc(sizeof(double) * 10000);
    *returnSize = 0;                    // 目前答案陣列長度為 0 / answer length starts at 0

    // 佇列：用一個指標陣列存放「待處理的節點」。
    // Queue: an array of node pointers holding nodes waiting to be processed.
    struct TreeNode** queue =
        (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10000);
    int head = 0, tail = 0;             // head=下一個要取出的位置, tail=下一個要放入的位置
                                        // head = next to remove, tail = next to insert

    queue[tail++] = root;               // 把根節點放進佇列 / enqueue the root

    // 只要佇列裡還有節點，就代表還有一層要處理。
    // While the queue is non-empty, there is still a level to process.
    while (head < tail) {
        int levelSize = tail - head;    // 凍結這一層的節點數量 / snapshot this level's size
        long long sum = 0;              // 用 64 位元整數累加，避免溢位 / 64-bit sum avoids overflow

        // 精確地處理 levelSize 個節點（就是這一層的所有節點）。
        // Process exactly levelSize nodes (all nodes on this level).
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = queue[head++];  // 出佇列取一個節點 / dequeue one node
            sum += node->val;           // 累加它的值（-> 是取指標指向的結構成員）/ add its value

            // 若有左孩子，放進佇列（它屬於下一層）。
            // If a left child exists, enqueue it (it belongs to the next level).
            if (node->left)  queue[tail++] = node->left;
            // 右孩子同理 / same for the right child
            if (node->right) queue[tail++] = node->right;
        }

        // 這一層的平均 = 總和 / 節點數。
        // (double)sum 讓除法變成浮點除法，才能得到小數。
        // Average = sum / count; casting to double gives real (decimal) division.
        res[(*returnSize)++] = (double)sum / levelSize;
    }

    free(queue);                        // 釋放佇列記憶體，避免記憶體洩漏 / free the queue memory
    return res;                         // 回傳答案陣列 / return the answer array
}