题目描述：

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

输入输出样例：

示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：

示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：

示例 3：
输入：root = [1,null,3]
输出：[1,3]

示例 4：
输入：root = []
输出：[]

提示：
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

题解：

解题思路：

思路一（层次遍历）：

1、采用层次遍历的方法记录每层的最后一个结点。将每层的节点数进行统计，将这层的所有孩子结点进队之后，队尾的结点就是下一层的最右侧的结点。

2、复杂度分析：
① 时间复杂度：O(n)。其中 n 是二叉树的节点个数，需遍历整颗二叉树。

② 空间复杂度：O(n)。每个节点最多进队列一次，所以队列长度最大不超过 n，所以这里的空间代价为 O(n)（再具体一点可以说是树的最大宽度）。

思路二（递归先访问右子树）：

1、通过递归先访问右子树，我们每一层中第一个访问的结点便为二叉树的右结点，所以我们只需记录到达下一层第一个访问的结点。

2、复杂度分析
① 时间复杂度：O(n)，其中 n 是二叉树的节点个数，需遍历整颗二叉树。

② 空间复杂度：O(h)，其中 h 是二叉树的高度。递归需要 O(h) 的栈空间。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。

代码实现

代码实现（思路一（层次遍历））：

//方法一：采用层次遍历的方法记录每层的最后一个结点
vector<int> rightSideView1(TreeNode* root) {
    vector<int> ans;
    if(root==nullptr) return ans;
    queue<TreeNode *> q;
    q.push(root);
    ans.emplace_back(root->val);
    while (!q.empty())
    {
    	//存储一层的结点数
        int size=q.size();
        for (int i = 0; i < size; i++)
        {
            root=q.front();
            q.pop();
            if (root->left!=nullptr) q.push(root->left);
            if(root->right!=nullptr) q.push(root->right);
        }
		//排除最后q为空的情况，添加完一层结点后，q的尾结点就是最右侧的结点。
        if (!q.empty()) ans.emplace_back(q.back()->val);
        
    }
    
    return ans;
}

代码实现（思路二（递归先访问右子树））：

//方法二：递归,通过递归先访问右子树，我们记录每一层中第一个访问的结点便为二叉树的右结点
vector<int> rightSideView2(TreeNode* root) {
    vector<int>ans;
    dfs(root,0,ans);
    return ans;
}

void dfs(TreeNode *root,int depth,vector<int> &ans){
    if(root==nullptr) return;
    //当深度和数组大小相同，添加结点值（添加后数组大小会增加）
    if(ans.size()==depth) ans.emplace_back(root->val);
    //先遍历右子树，每向下递归深度增加
    dfs(root->right,depth+1,ans);
    dfs(root->left,depth+1,ans);
}

以思路一为例进行调试

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int val):val(val),left(nullptr),right(nullptr){}
    TreeNode(int val,TreeNode *left,TreeNode *right):val(val),left(left),right(right){}
};

//通过数组创建二叉树，数组中-1代表nullptr
TreeNode *createTree(vector <int> nums){
    if (nums.empty()) return nullptr;
    TreeNode *root=new TreeNode(nums[0]);
    queue<TreeNode *> q;
    q.push(root);
    int i=1;
    while (i<nums.size())
    {
        //注意这里不能用root,会改变root的指向
        TreeNode *node=q.front();
        q.pop();
        if(i<nums.size()&&nums[i]!=-1){
            node->left=new TreeNode(nums[i]);
            q.push(node->left);
        }
        ++i;
        if(i<nums.size()&&nums[i]!=-1){
            node->right=new TreeNode(nums[i]);
            q.push(node->right);
        }
        ++i;
    }
    
    return root;
}

//中序遍历输出二叉树，用于验证二叉树是否创建正确
void inorder(TreeNode *root){
    if(root==nullptr) return;   
    inorder(root->left);
    cout<<root->val<<" ";
    inorder(root->right);
}

class Solution
{
public:
    //方法一：采用层次遍历的方法记录每层的最后一个结点
    vector<int> rightSideView1(TreeNode* root) {
        vector<int> ans;
        if(root==nullptr) return ans;
        queue<TreeNode *> q;
        q.push(root);
        ans.emplace_back(root->val);
        while (!q.empty())
        {
            int size=q.size();
            for (int i = 0; i < size; i++)
            {
                root=q.front();
                q.pop();
                if (root->left!=nullptr) q.push(root->left);
                if(root->right!=nullptr) q.push(root->right);
            }

            if (!q.empty()) ans.emplace_back(q.back()->val);
            
        }
        
        return ans;
    }

};

int main(){
    vector<int> nums={1,2,3,-1,5,-1,4};
    //创建二叉树
    TreeNode* root=createTree(nums);
    //测试二叉树是否创建正确
    //inorder(root);
    
    Solution s;
    //形成二叉树的右视图
    vector<int> ans=s.rightSideView1(root);
    
    //输出二叉树最右侧结点的值
    for (auto &i : ans)
    {
        cout<<i<<" ";
    }
    return 0;
}

LeetCode 热题 100_二叉树的右视图（45_199)原题链接
欢迎大家和我沟通交流(✿◠‿◠)