199. Binary Tree Right Side View

這題我一開始看到小傻眼, 不過後來就想到我們可以記錄一張表, 表示高度跟是哪個值, 我們一律都從右邊去dfs, 先看到誰就紀錄誰, 然後掃遍整個tree, 最後我們在看表的記錄每個高度的值就可以了, 答案要求要ordered, 所以我們用map

class Solution {
public:
    void dfs(TreeNode* root, int height, map<int, int> &table){
        if(table.count(height) == 0){
            table[height] = root->val;
        }
        if(root->right){
            dfs(root->right, height + 1, table);
        }
        if(root->left){
            dfs(root->left, height + 1, table);
        }
    }
    vector<int> rightSideView(TreeNode* root) {
        if(!root){
            return vector<int>();
        }
        map<int, int> table;
        dfs(root, 0, table);
        vector<int> ans;
        for(auto a: table){
            ans.push_back(a.second);
        }
        return ans;
    }
};

bfs:

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root){
            return {};
        }
        map<int, int> table;
        queue<TreeNode*> q;
        int height = 0;
        q.push(root);
        while(!q.empty()){
            int size= q.size();
            height++;
            for(int i=0; i < size;i++){
                TreeNode *cur = q.front();
                q.pop();
                if(!table.count(height)){
                    table[height] = cur->val;
                }
                if(cur->right){
                    q.push(cur->right);
                }
                if(cur->left){
                    q.push(cur->left);
                }
            }
        }
        vector<int> ans;
        for(auto &a: table){
            ans.push_back(a.second);
        }
        return ans;
    }
};