102. Binary Tree Level Order Traversal

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

        3          <- level 0
       / \
      9  20        <- level 1
        /  \
       15   7      <- level 2

Output: [[3], [9,20], [15,7]]

/*
 * 演算法 / Algorithm: BFS with a queue (廣度優先搜尋 + 佇列).
 * 用陣列當佇列，一次處理一整層；每層開始時先鎖定該層節點數 size，
 * We use an array as a FIFO queue and process one full level per outer loop,
 * snapshotting the level's node count (size) before popping so levels don't mix.
 */

/* LeetCode 提供的節點定義（此處僅為說明，實際由平台給出）
 * struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };
 */

/**
 * 回傳一個 int** (指向多個 int 陣列的指標)，每個子陣列是一層。
 * Returns int** : an array of int arrays, one per level.
 * returnSize:        寫回總共有幾層 / how many levels (rows) there are.
 * returnColumnSizes: 寫回每一層各有幾個元素 / length of each row.
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    // 樹最多 2000 個節點，先為結果與佇列預留足夠空間。
    // At most 2000 nodes; reserve enough room for results and the queue up front.
    int** answer = (int**)malloc(sizeof(int*) * 2000);       // answer[i] 指向第 i 層的值陣列 / answer[i] = values of level i
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);   // 每層長度的陣列 / array holding each level's length
    *returnSize = 0;                                          // 目前收集到的層數，先設 0 / levels collected so far

    // 空樹：沒有任何層，直接回傳。 Empty tree: no levels, return immediately.
    if (root == NULL) return answer;

    // 用固定大小陣列當佇列。head 指向下一個要取出的位置，tail 指向下一個要放入的位置。
    // A fixed-size array as the queue: head = next to pop, tail = next to push.
    struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 2000);
    int head = 0, tail = 0;                                   // 佇列一開始是空的 / queue starts empty

    queue[tail++] = root;                                     // 把根節點放進佇列尾 / enqueue the root (tail++ 先用再加一 / use then increment)

    // 只要佇列還有節點，就代表還有一層要處理。
    // While the queue is non-empty, there is another level to process.
    while (head < tail) {
        int size = tail - head;                              // 關鍵：先鎖定本層節點數 / snapshot THIS level's node count
        int* level = (int*)malloc(sizeof(int) * size);       // 本層的值陣列，長度剛好 size / this level's values, length size
        int k = 0;                                            // k 是本層陣列的下一個寫入位置 / next write slot in level[]

        // 正好取出 size 個節點，就是完整的一層。
        // Pop exactly `size` nodes — that is one complete level.
        for (int i = 0; i < size; i++) {
            struct TreeNode* node = queue[head++];           // 取出佇列最前面的節點 / dequeue front node (head++ 前進 / advance head)
            level[k++] = node->val;                          // 記下它的值；node->val 是「順著指標拿 val 欄位」/ record its value (-> dereferences the pointer)

            // 把左右子節點推進佇列，它們屬於「下一層」。
            // Push children onto the queue; they belong to the NEXT level.
            if (node->left)  queue[tail++] = node->left;      // 有左子節點才放 / enqueue left child if it exists
            if (node->right) queue[tail++] = node->right;     // 有右子節點才放 / enqueue right child if it exists
        }

        answer[*returnSize] = level;                         // 把本層陣列存進結果 / store this level's array
        (*returnColumnSizes)[*returnSize] = size;            // 記下本層長度 / record this level's length
        (*returnSize)++;                                     // 層數加一 / one more level collected
    }

    free(queue);                                             // 佇列用完了，釋放記憶體 / done with the queue, free it
    return answer;                                           // 回傳所有層 / return all levels
}

/*
 * 演算法 / Algorithm: BFS with std::queue (廣度優先搜尋 + 佇列).
 * 每一輪外層迴圈用 q.size() 鎖定當前層的節點數，處理完剛好留下下一層。
 * Each outer loop uses q.size() to lock the current level's count, leaving
 * exactly the next level in the queue afterward.
 */

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> answer;          // 最終答案，每個元素是一層 / result; each element is one level
        if (root == nullptr) return answer;  // 空樹直接回空陣列 / empty tree → empty result

        queue<TreeNode*> q;                   // std::queue 是先進先出容器 / std::queue is a FIFO container
        q.push(root);                         // 根節點入列 / enqueue the root

        // 佇列非空代表還有下一層要處理。
        // A non-empty queue means another level remains.
        while (!q.empty()) {
            int size = q.size();              // 關鍵：先記本層節點數 / snapshot THIS level's node count
            vector<int> level;                // 收集本層的值 / values for this level
            level.reserve(size);              // 預留空間避免多次重新配置 / reserve to avoid reallocations (小優化 / minor optimization)

            // 正好處理 size 個節點 = 完整一層。
            // Process exactly `size` nodes = one full level.
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();   // 看佇列最前面的節點 / read the front node
                q.pop();                      // 把它移出佇列 / remove it from the queue
                level.push_back(node->val);   // 記下它的值 / record its value

                // 子節點屬於下一層，推到佇列尾。
                // Children belong to the next level; push them to the back.
                if (node->left)  q.push(node->left);   // 有左子節點才入列 / enqueue left child if present
                if (node->right) q.push(node->right);  // 有右子節點才入列 / enqueue right child if present
            }

            answer.push_back(move(level));    // 本層完成，收進答案；move 避免複製 / append level; move() transfers instead of copying
        }

        return answer;                        // 回傳逐層結果 / return level-by-level result
    }
};