/*
 * 演算法 / Algorithm: BFS 層序遍歷。用佇列一層一層走，每層記下最後彈出的節點（最右）。
 * BFS level-order: walk level by level with a queue; record the last node popped
 * on each level (the rightmost one). Each node is visited exactly once -> O(n).
 */

/**
 * Definition for a binary tree node.  (LeetCode 已提供 / provided by LeetCode)
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/* 回傳一個 int 陣列；透過 *returnSize 告訴呼叫方陣列長度。
 * Return an int array; report its length via *returnSize (an out-parameter). */
int* rightSideView(struct TreeNode* root, int* returnSize) {
    /* 樹最多 100 個節點，答案最多 100 個（每層一個）。先配置足夠空間。
     * At most 100 nodes -> at most 100 levels -> answer size <= 100. Allocate enough. */
    int* ans = (int*)malloc(sizeof(int) * 100); /* malloc 向系統要一塊記憶體 / ask OS for memory */
    *returnSize = 0;                            /* 目前答案長度為 0 / answer length starts at 0 */

    /* 空樹：直接回傳長度為 0 的陣列 / Empty tree: return an array of length 0. */
    if (root == NULL) return ans;

    /* 用一個陣列當作佇列；queue[head..tail-1] 是目前佇列內容。
     * Use an array as a queue; queue[head..tail-1] holds the current elements. */
    struct TreeNode* queue[100];  /* 佇列最多同時裝 100 個節點指標 / holds up to 100 node pointers */
    int head = 0;                 /* 佇列頭（下一個要取出的位置）/ front index (next to pop) */
    int tail = 0;                 /* 佇列尾（下一個要放入的位置）/ back index (next write slot) */

    queue[tail++] = root;         /* 把根節點放入佇列；tail++ 先用後加一 / enqueue root; post-increment */

    /* 只要佇列非空，就還有層要處理 / While the queue is non-empty, more levels remain. */
    while (head < tail) {
        int size = tail - head;   /* 這一層的節點數量 = 目前佇列大小 / count of nodes on this level */

        /* 依序彈出這一層的所有節點（由左到右）/ Pop all nodes of this level, left to right. */
        for (int i = 0; i < size; i++) {
            struct TreeNode* node = queue[head++]; /* 取出佇列頭；head++ 表示已消耗一個 / dequeue front */

            /* 這一層的最後一個節點（i == size-1）就是最右邊，加入答案。
             * The last node of this level (i == size-1) is the rightmost -> record it. */
            if (i == size - 1) {
                ans[(*returnSize)++] = node->val; /* node->val 透過指標讀取值 / read val via pointer */
            }

            /* 把孩子加入佇列，形成下一層（先左後右）。
             * Enqueue children to form the next level (left first, then right). */
            if (node->left)  queue[tail++] = node->left;  /* 有左孩子才放 / only if left exists */
            if (node->right) queue[tail++] = node->right; /* 有右孩子才放 / only if right exists */
        }
    }

    return ans; /* 呼叫方會依 *returnSize 讀取前面幾個元素 / caller reads *returnSize elements */
}