迭代

按照层序遍历，每一层最右边的元素就是二叉树右视图的元素。迭代算法需要队列保存二叉树每一层的所有结点，并且在遍历下一层时，上一层的所有结点已经出队。在遍历下一层之前，记录队列大小，即为二叉树当前层的结点数量。从而找到最后一个结点。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(q.size()){
            int len = q.size();
            for(int i = 0;i<len;i++){
                auto t = q.front();
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
                if(i == len - 1) ans.push_back(t->val);
            }
        }
        return ans;
    }
};

1. 时间复杂度 : $O(n)$ ， $n$ 是二叉树的结点数，每个结点最多入队一次，时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(h)$ ， $h$ 是二叉树的深度，队列内元素最大数量为 $O(h)$ 。
   

递归

考虑这样的递归方式 : 根右左，将递归压栈每一层的第一个元素加入答案，即为二叉树的右视图。仅当第一次进入下一层时，答案加入元素。我们可以记录层数信息，和答案数量比较。根结点记作第 $0$ 层，仅当答案数量$=$层数，维护答案。

class Solution {
public:
    vector<int> ans;
    vector<int> rightSideView(TreeNode* root) {
        dfs(root,0);
        return ans;
    }
    void dfs(TreeNode *root,int depth){
        if(!root) return;
        if(depth==ans.size()) ans.push_back(root->val);
        dfs(root->right,depth+1);
        dfs(root->left,depth+1);
    }
};

1. 时间复杂度 : $O(n)$ ， $n$ 是二叉树的结点数，最多递归每个结点一次，时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(h)$ ， $h$ 是二叉树的深度，函数压栈的最大深度为 $O(h)$ 。
   

致语

• 理解思路很重要！
• 欢迎读者在评论区留言，墨染看到就会回复的。