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