/*
 * 演算法 / Algorithm: BFS 層序遍歷。用 std::queue 一層一層走，
 * 每層取最後一個節點（最右）的值。每個節點只處理一次 -> O(n)。
 * BFS level-order with std::queue; take the last node's value on each level.
 */

/**
 * Definition for a binary tree node.  (LeetCode 已提供 / provided by LeetCode)
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     ...
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;                 /* 動態陣列，存放答案 / dynamic array for the answer */
        if (root == nullptr) return ans; /* 空樹回傳空陣列 / empty tree -> empty result */

        /* std::queue 是 STL 的佇列（先進先出），適合 BFS。
         * std::queue is the STL FIFO queue, perfect for BFS. */
        queue<TreeNode*> q;
        q.push(root);                    /* 根節點入佇列 / enqueue the root */

        /* 佇列非空代表還有節點沒處理 / Non-empty queue means levels remain. */
        while (!q.empty()) {
            int size = q.size();         /* 固定住這一層的節點數 / freeze this level's node count */

            /* 逐一處理這一層（由左到右）/ Process this level, left to right. */
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front(); /* 讀取佇列最前面的節點 / peek the front node */
                q.pop();                    /* 將它移出佇列 / remove it from the queue */

                /* 這層最後一個節點即最右，記錄其值。
                 * The last node this level is the rightmost -> record it. */
                if (i == size - 1) ans.push_back(node->val); /* push_back 尾端加入 / append */

                /* 把孩子放入佇列作為下一層（先左後右）。
                 * Enqueue children for the next level (left then right). */
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }

        return ans; /* 由上而下的最右節點值 / rightmost values, top to bottom */
    }
};