Problem :

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1 :

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

Example 2 :

Input: root = [1]
Output: [[1]]

Example 3 :

Input: root = []
Output: []

核心思維 :

1. 檢查根節點是否為空，若為空則回傳空的結果
2. 將陣列初始化以儲存最右邊的節點值
3. 利用佇列遍歷二元樹，並將根節點放入佇列當中
4. 當佇列不為空，計算當前所處層的節點數量遍歷
5. 遍歷所處層的所有節點並取出佇列的前端節點

• 若當前節點為當前層的最後一個節點，則將此節點值儲存
• 若該節點的左子節點不為空，則將左子節點加入佇列
• 若該節點的右子節點不為空，則將右子節點加入佇列

6. 回傳儲存的結果

程式碼 :

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        //若根節點為空則回傳空的結果
        if(root == nullptr){
            return {};
        }
        //陣列初始化並用來儲存最右邊的節點值
        vector<int> result;
        //利用佇列遍歷二元樹
        queue<TreeNode*> q;
        //將根節點放入佇列當中
        q.push(root);
        //當佇列不為空，計算當前所處層的節點數量
        while(!q.empty()){
            int size = q.size();
            //遍歷當前所處層的所有節點
            for(int i = 0; i < size; i++){
                //取出佇列的前端節點
                TreeNode *node = q.front();
                q.pop();
                //若當前節點為當前層的最後一個節點，則將此節點值儲存
                if(i == size - 1){
                    result.push_back(node -> val);
                }
                //若該節點的左子節點不為空，則將左子節點加入佇列
                if(node -> left){
                    q.push(node -> left);
                }
                //若該節點的右子節點不為空，則將右子節點加入佇列
                if(node -> right){
                    q.push(node -> right);
                }
            }
        }
        //回傳儲存的結果
        return result;
    }
};

結論 :

這題的目標是將二元樹的最右邊節點回傳，可以想像你站在一棵大樹的右側，並從側面觀察這棵樹的結構。你無法看到樹的所有節點，但能清楚地看到每層的最右邊節點。解題方法是每次遍歷一層時，儲存該層的最右邊節點值，並將下一層的所有子節點加入佇列中，重複這個過程直到遍歷完整棵樹。