# Leetcode [No. 199] Binary Tree Right Side View (MEDIUM)

+ Solved on 2024/02/21
+ Solved 2nd on 2025/04/27
## 題目

https://leetcode.com/problems/binary-tree-right-side-view/description/

## 思路

+ 使用DFS，只記錄最右邊的node (WA)

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        rightSideDFS(root,res);
        return res;
    }
    void rightSideDFS(TreeNode* node, vector<int>& res)
    {
        if(!node)
        {
            return;
        }
        res.emplace_back(node->val);
        if(node->right)
        {
            rightSideDFS(node->right, res);
        }
        else
        {
            rightSideDFS(node->left, res);
        }
    }
};

+ 這個寫法會錯在如果最深的node在左子樹，正確答案為[1,3,4]，而我只會return[1,3]
+ 

### 解法分析
+ time complexity: O(lgn)

### 執行結果

## 修正:

+ 改成使用BFS，但只記錄最右邊的node

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        rightSideBFS(root,res);
        return res;
    }
    void rightSideBFS(TreeNode* node, vector<int>& res)
    {
        if(!node) return;
        queue<TreeNode*> q;
        q.push(node);
        while(!q.empty())
        {
            int qSize = q.size();
            for(int i = 0 ; i < qSize; i++)
            {
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left)
                {
                    q.push(cur->left);
                }
                if(cur->right)
                {
                    q.push(cur->right);
                }
                if(i == qSize-1) res.emplace_back(cur->val);
            }
        }
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

## 改良

+ 因為發現BFS大概只能解到20%
+ 改成使用reversePreOrderTraversal就會是正確答案了~
+ 只不過需要注意level的問題，要抓緊時間push

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        reversePreOrder(root,res, 0);
        return res;
    }
    void reversePreOrder(TreeNode* node, vector<int>& res, int level)
    {
        if(!node) return;
        // cout << node->val << " ";
        if(res.size() == level) res.emplace_back(node->val);
        reversePreOrder(node->right, res, level+1);
        reversePreOrder(node->left, res, level + 1) ;
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

## 二訪@2025/04/27

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* cur = q.front();
                q.pop();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
                if (i == size-1) res.emplace_back(cur->val);
            }
        }
        return res;
    }
};

用levelOrderTraversal秒殺