199. Binary Tree Right Side View

題目 / Problem

中文： 給定一棵二元樹的根節點 root，想像你站在這棵樹的右側，由上而下回傳你能看到的節點值。也就是說，對於每一層，你只能看到最右邊的那個節點。

English: Given the root of a binary tree, imagine standing on the right side of it. Return the values of the nodes you can see, ordered from top to bottom. In other words, for each level of the tree, you can only see its rightmost node.

Constraints / 限制： - 樹中節點數量範圍為 [0, 100]（可能是空樹）/ The number of nodes is in the range [0, 100] (the tree may be empty). - -100 <= Node.val <= 100。

Worked example / 範例： - Input: root = [1,2,3,null,5,null,4] - Output: [1,3,4] - 這棵樹長這樣 / The tree looks like: 1 <- level 0, rightmost = 1 / \ 2 3 <- level 1, rightmost = 3 \ \ 5 4 <- level 2, rightmost = 4 從右邊看，每一層最右邊的節點是 1、3、4 / Viewed from the right, the rightmost node of each level is 1, 3, 4.

名詞解釋 / Glossary

• 二元樹 / Binary tree：每個節點最多有兩個子節點，稱為左子節點（left）和右子節點（right）。/ A tree where each node has at most two children, called left and right.
• 層序遍歷 / Level-order traversal (BFS)：一種從上到下、每層由左到右逐層走訪節點的方法，也叫廣度優先搜尋。/ A way of visiting nodes level by level, top to bottom and left to right; also called Breadth-First Search.
• 佇列 / Queue：一種「先進先出」（FIFO）的資料結構，先放進去的元素先被取出，非常適合做 BFS。/ A First-In-First-Out data structure; the first element added is the first removed — ideal for BFS.
• 深度優先搜尋 / Depth-First Search (DFS)：一種沿著一條路徑一直往下走到底、再回頭的走訪方式；本題也可用「先走右邊」的 DFS 解。/ A traversal that goes as deep as possible along a path before backtracking; this problem can also be solved by a "right-first" DFS.
• 指標 / Pointer：C/C++ 中儲存「記憶體位址」的變數；node->val 表示透過指標存取節點的值。/ A variable that stores a memory address; node->val accesses a field of the node through its pointer.
• 動態陣列 / Dynamic array (vector)：C++ STL 提供的可自動增長的陣列，push_back 在尾端加入元素。/ An auto-resizing array from the C++ STL; push_back appends an element to the end.

思路

最直覺的想法是逐層處理這棵樹：既然「右側視角」看到的其實就是每一層最右邊的節點，那我只要能一層一層地走訪，並在每層記下最後一個節點的值就好。要做到「一層一層走」，最自然的工具是佇列（Queue）配合廣度優先搜尋（BFS）。做法是：先把根節點放進佇列，然後重複「處理一整層」這個動作。在處理某一層之前，先記錄目前佇列裡的元素個數 size，這個數字剛好就是「這一層有多少節點」。接著我們把這 size 個節點依序取出，取的順序是由左到右，因此當我們取到第 size 個（也就是這層最後一個）節點時，它就是這一層最右邊的節點，把它的值加入答案。每取出一個節點，就把它的左、右子節點（若存在）加入佇列，作為下一層的節點。為什麼記錄 size 很重要？因為在處理過程中我們會不斷把下一層的節點塞進佇列，如果不先固定住「這一層」的數量，就會分不清哪些屬於當前層、哪些屬於下一層。這個 BFS 每個節點只進出佇列一次，時間複雜度是 O(n)，非常高效。

The most natural idea is to process the tree level by level: the "right side view" is exactly the rightmost node of each level, so if I can walk the tree one level at a time and remember the last node on each level, I'm done. The classic tool for level-by-level walking is a queue with Breadth-First Search (BFS). Start by pushing the root into the queue, then repeat the step "process one entire level." Before processing a level, record size, the current number of nodes in the queue — this is exactly how many nodes are on this level. Then pop those size nodes one by one in left-to-right order; because of this order, the last one popped (the size-th) is the rightmost node of that level, so we record its value. As we pop each node, we push its left and right children (if any) into the queue to form the next level. Why is snapshotting size essential? Because while processing a level we keep adding the next level's nodes to the same queue; if we don't freeze the current level's count first, we can't tell where one level ends and the next begins. Each node enters and leaves the queue exactly once, so this runs in O(n) time — very efficient.

逐步走查 / Walkthrough

Input: root = [1,2,3,null,5,null,4] — the tree drawn above.

We use a queue q and an answer list ans. size = number of nodes to pop for the current level.

• Level 0：佇列只有 1，它就是最右，答案加 1。它的孩子 2,3 進佇列。/ Only node 1; it's the rightmost. Push children 2,3.
• Level 1：固定 size=2，依序彈出 2、3。3 是這層最後一個 → 加入答案。彈 2 時把 5 推入，彈 3 時把 4 推入。/ Freeze size=2, pop 2 then 3; 3 is last → added. 2 pushes 5, 3 pushes 4.
• Level 2：彈出 5、4，4 是最後一個 → 加入答案。兩者皆為葉節點，無子節點。/ Pop 5,4; 4 is last → added. Both are leaves.
• 佇列空了，結束，答案為 [1,3,4]。/ Queue is empty; final answer [1,3,4].

Solution — C

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

Solution — C++

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

複雜度 / Complexity

• Time: O(n) — n 是節點總數。每個節點恰好被放入佇列一次、取出一次，做的都是常數時間操作，所以總時間與節點數成正比。/ n is the number of nodes. Each node is enqueued and dequeued exactly once, doing constant work, so total time is proportional to the node count.
• Space: O(n) — 佇列在最壞情況（最寬的一層，如完滿樹的最底層）可能同時存放約 n/2 個節點，屬於 O(n)；答案陣列最多存每層一個節點。/ In the worst case (the widest level, e.g. the bottom of a full tree) the queue holds up to ~n/2 nodes, i.e. O(n); the answer stores at most one node per level.

Pitfalls & Edge Cases

• 空樹 / Empty tree (root == NULL)：必須先檢查，否則會對空指標解參考而崩潰。程式碼一開始就 return 空結果。/ Must check first, otherwise you dereference a null pointer and crash. The code returns an empty result immediately.
• 忘記固定 size / Not snapshotting the level size：若在迴圈中直接用 q.size()（C++）或 tail - head（C）作為條件，處理當前層時推入的下一層節點會被誤算進來，導致跨層混亂。先存成 size 就把每一層清楚切開。/ If you use the live queue size as the loop bound, children pushed during the level get mixed in, blurring level boundaries. Storing size first cleanly separates each level.
• 「最右」不一定是右子節點 / "Rightmost" isn't always a right child：如範例，某層最右的節點可能來自左子樹（因為右子樹在該層沒有節點）。用「每層最後彈出者」判斷才正確，不能只沿著 right 指標走。/ The rightmost node on a level can come from a left subtree (Example: 4 sits under 3's right, but on other trees the visible node may be a left child). Taking the last node popped per level is correct; blindly following right pointers is not.
• C 的 *returnSize / The out-parameter in C：LeetCode 用 *returnSize 回報陣列長度，忘了設定會讓評測讀到錯誤長度。務必每加入一個值就同步 (*returnSize)++。/ LeetCode reports the array length via *returnSize; forgetting to set it makes the grader read a wrong length. Increment it in lockstep with each value added.
• 佇列容量 / Queue capacity (C)：本題節點上限 100，固定大小 queue[100] 已足夠；若上限更大則需動態配置以免越界。/ With at most 100 nodes, a fixed queue[100] is safe; for larger limits you'd need dynamic allocation to avoid overflow.