书到用时方恨少，枉我最近一直在疯狂刷题找状态，没想到关键时刻还是掉链子了。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例：

• 输入: [1,2,3,null,5,null,4]
• 输出: [1, 3, 4]
• 解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

二、题解

2.1 广度优先遍历

看到题目第一个想到的就是广度优先遍历，因为右视图看到的都是每一层最右边的节点，直接通过广搜层次遍历，然后取每层最后元素即可。

2.2 深搜+递归

深搜的过程：一直读右子树的节点，直到右子树不存在，然后遍历左子树。同时，给每层数据都加上层数标记，因为遍历了右子树后还需要遍历左子树，如果当前层已经找过到了最右边的节点，就继续往下找。

三、代码

广搜代码

class Solution {
public:
    vector<int> rightSideView(TreeNode *root) {
        int i, n;
        queue<TreeNode *> q;
        TreeNode *p;
        vector<int> ans;

        if (root == nullptr) {
            return ans;
        }

        q.push(root);

        while (!q.empty()) {
            n = q.size();

            for (i = 0; i < n; i++) {
                p = q.front();
                q.pop();
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }

            ans.push_back(p->val);
        }

        return ans;
    }
};

深搜代码

class Solution {
private:
    void f(vector<int> &ans, int depth, TreeNode *root) {
        TreeNode *p;
        int n;

        if (root == nullptr)
            return;

        if (ans.size() <= depth) {
            ans.push_back(root->val);
        }

        if (root->right) {
            f(ans, depth + 1, root->right);
        }
        if (root->left) {
            f(ans, depth + 1, root->left);
        }
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        f(ans, 0, root);
        return ans;
    }
};