[数据结构与算法]LeetCode 199.二叉树的右视图（DFS和层序遍历 通俗易懂）

题目描述：

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

输入:?[1,2,3,null,5,null,4]
输出:?[1,3,4]

一、DFS实现

思路：

从根部开始向右搜索，定义一个step表示层数，从0开始，再定义一个vector容器res储存每一层的最右边的元素,直到最底层的最右边元素添加到res中。

代码：

class Solution {
public:
    vector<int> res;
    vector<int> rightSideView(TreeNode* root) {
        dfs(root,0); //从根部开始
        return res;
    }

    void dfs(TreeNode* root,int step){
        if(root==nullptr){
            return ; 
        }
        if(step==res.size()){ 
            res.push_back(root->val); //每一层的最后边的元素加入到容器中
        }
        dfs(root->right,step+1); //继续向右搜索
        dfs(root->left,step+1); //右边到达叶子节点时向左边搜索
    }
};

二、层序遍历实现

1.思路：

根据层序遍历的思想，每遍历一层的最右边的元素就是右视图中的元素。

2.代码：

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res; //储存符合条件的元素
        queue<TreeNode*> que; //队列实现层序遍历
        if(root!=nullptr){ //先将根节点加入队列
            que.push(root);
        }
        while(!que.empty()){ 
            int size=que.size(); //一定要把队列大小赋值给常量，因为队列大小在循环中一直会变化
            for(int i=0;i<size;i++){
                TreeNode* node=que.front(); 
                que.pop(); //出队列
                if(i==(size-1)){ //把每一层层序遍历的最后一个元素加入到容器中
                    res.push_back(node->val);
                }
                if (node->left!=nullptr){
                    que.push(node->left);
                }
                if (node->right!=nullptr){
                    que.push(node->right);
                } 
            }
        }
        return res;
    }
};

?