637. Average of Levels in Binary Tree

題目 / Problem

中文： 給定一棵二元樹的根節點 root，請回傳一個陣列，裡面依序放著每一層節點值的「平均值」。也就是說：第 0 層（只有根節點）的平均、第 1 層所有節點的平均、第 2 層所有節點的平均……以此類推。只要你的答案和標準答案的誤差在 10⁻⁵ 以內，就算正確。

English: Given the root of a binary tree, return an array where each element is the average value of the nodes on one level of the tree. Element 0 is the average of level 0 (just the root), element 1 is the average of level 1, and so on. Any answer within 10⁻⁵ of the true answer is accepted.

Constraints / 限制條件： - 節點數量介於 [1, 10⁴]（所以樹不會是空的 / the tree is never empty）。 - 每個節點的值 Node.val 介於 -2³¹ 到 2³¹ - 1（可能是很大的負數或正數 / values can be large, negative or positive).

Worked example / 範例：

Input:  root = [3,9,20,null,null,15,7]

        3          ← 層 0 / level 0
       / \
      9   20       ← 層 1 / level 1
         /  \
        15   7     ← 層 2 / level 2

Output: [3.00000, 14.50000, 11.00000]

• Level 0: 3 / 1 = 3
• Level 1: (9 + 20) / 2 = 14.5
• Level 2: (15 + 7) / 2 = 11

名詞解釋 / Glossary

• 二元樹 / Binary tree： 一種樹狀資料結構，每個節點最多有兩個子節點，分別叫做左子節點 left 和右子節點 right。A tree structure where every node has at most two children, called left and right.
• 節點 / Node： 樹裡的一個元素，內含一個整數值 val，以及指向左右子節點的指標。An element of the tree holding an integer val plus pointers to its two children.
• 層 / Level（深度 depth）： 從根節點到某節點所經過的邊數。根節點是第 0 層，它的孩子是第 1 層。The distance (in edges) from the root; the root is level 0, its children are level 1, etc.
• 廣度優先搜尋 / BFS (Breadth-First Search)： 一種「一層一層」走訪樹的方法——先看完這一層的所有節點，再進到下一層。A traversal that visits the tree level by level, finishing one whole level before moving deeper.
• 佇列 / Queue： 一種「先進先出 (FIFO)」的容器：最早放進去的元素最早被取出，就像排隊。BFS 用它來記住「還沒處理的節點」。A first-in-first-out container — the earliest inserted item is the first removed, like a line of people. BFS uses it to remember nodes waiting to be processed.
• 雙精度浮點數 / double： 一種能存小數的資料型別，因為平均值可能不是整數（例如 14.5）。A floating-point type that can hold decimals, needed because averages like 14.5 aren't whole numbers.
• long long（64 位元整數 / 64-bit integer）： 一種能存超大整數的型別，用來累加同一層的節點值，避免相加時「溢位」。A big integer type used to sum node values on a level without overflow.

思路

中文： 這題的核心是「把樹一層一層地處理」。最直覺的暴力想法可能是：先用某種方式算出每個節點在第幾層（例如做一次 DFS 記下每個節點的深度），再把相同深度的值分組加總、算平均。這樣可行，但要額外管理「深度 → 值的清單」的對應關係，程式碼比較繁瑣。更自然的作法是「廣度優先搜尋 (BFS)」，因為 BFS 本來就是一層一層往下走的。關鍵技巧在於：我們用一個佇列存放「當前這一層」的所有節點。當我們準備處理某一層時，先記下此刻佇列裡有幾個節點（假設是 count 個），這個 count 就正好是這一層的節點數量。接著我們就精確地做 count 次「取出一個節點」的動作：把它的值累加起來，同時把它的左右孩子放進佇列（它們就是下一層）。做完這 count 次，我們就把「這一層的總和 ÷ count」這個平均值存進答案。之所以要在迴圈開始前先固定 count，是因為在處理過程中我們會不斷把下一層的孩子加進佇列，如果不先記住數量，就會分不清哪些是這一層、哪些是下一層。累加時要用 64 位元整數 (long long)，因為節點值可能接近 ±2³¹，一層有上萬個這種值相加會超出 32 位元整數的範圍。

English: The heart of this problem is processing the tree one level at a time. A brute-force idea would be to first compute each node's depth (say, via a DFS that tags every node with its level), then group values by depth and average each group — workable, but it forces you to juggle a depth-to-values mapping. A cleaner fit is Breadth-First Search (BFS), because BFS is inherently level-by-level. The key trick: keep a queue holding the nodes of the "current level." Right before processing a level, record how many nodes are currently in the queue — call it count. That number is exactly the size of this level. Then do exactly count dequeue operations: for each node pulled out, add its value to a running sum and push its left and right children into the queue (those children form the next level). After the count iterations, store sum / count as this level's average. The reason we snapshot count before the loop is that we keep adding next-level children during the loop; without freezing the count first, we couldn't tell where the current level ends and the next begins. Accumulate the sum in a 64-bit integer (long long), because a single value can be near ±2³¹ and summing up to 10⁴ of them would overflow a 32-bit int.

逐步走查 / Walkthrough

Input: root = [3,9,20,null,null,15,7]. 我們用一個佇列 q，答案存在 res。/ We use a queue q, answers collected in res.

注意每一層開始前，count 都先「凍結」成當時佇列的大小，這樣才能把當前層和被加進來的下一層孩子分開。/ Notice that at each level's start, count is frozen to the queue's current size, cleanly separating the current level from the next-level children being added.

Solution — C

/*
 * 演算法 / 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
}

Solution — C++

/*
 * 演算法 / 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
    }
};

複雜度 / Complexity

• Time: O(n) — 其中 n 是節點總數。每個節點只會被放入佇列一次、取出一次並處理一次，所以總工作量和節點數成正比。/ where n is the number of nodes. Each node is enqueued, dequeued, and processed exactly once, so total work is proportional to the node count.
• Space: O(w) — w 是樹「最寬那一層」的節點數，因為佇列最多同時裝下一整層的節點。最壞情況（完美平衡樹的最底層）約有 n/2 個節點，所以最壞是 O(n)。/ w is the width of the widest level, since the queue holds at most one full level at a time. In the worst case (the bottom of a perfectly balanced tree) that's about n/2, i.e. O(n).

Pitfalls & Edge Cases

• 整數溢位 / Integer overflow： 一個節點值可達 ±2³¹，一層可能有上萬個節點。若用 32 位元 int 累加會溢位、算出錯誤結果。程式用 long long（64 位元）累加來避免。A single value can be near ±2³¹ and a level may hold thousands of nodes; summing in a 32-bit int overflows. We accumulate in long long.
• 整數除法陷阱 / Integer division trap： 若寫 sum / levelSize 而兩者都是整數，C/C++ 會做整數除法，29 / 2 得到 14 而非 14.5。務必先把分子轉成 double（(double)sum / static_cast<double>(sum)）。Dividing two integers truncates; cast the numerator to double first.
• 必須凍結 levelSize / Freeze the level size： 迴圈裡會把下一層孩子加進佇列，佇列大小持續變動。一定要在迴圈前把 levelSize 記下來，否則會把下一層混進這一層。The queue grows during the loop; snapshot the size before looping or you'll mix levels.
• 空樹 / Empty tree： 題目保證至少 1 個節點，但 C++ 版仍加了 root == nullptr 的保護，養成好習慣避免對空指標解參考。The constraints guarantee ≥1 node, but guarding against nullptr is good practice.
• 只有一個節點 / Single node： 樹只有 root 時，答案就是 [root->val]——BFS 自然處理，不需特例。A one-node tree yields [root->val]; BFS handles it with no special case.