199. 二叉树的右视图【 力扣(LeetCode) 】

零、原题链接

199. 二叉树的右视图

一、题目描述

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

二、测试用例

示例 1:

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

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

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

三、解题思路

1. 基本思路：
     基本就是暴力了，深度搜索或者广度搜索都可以，不过广度搜索好理解一点；
2. 具体思路：
   • 使用队列进行广度搜索
     • 弹出队首元素，如果左右子树非空，则将左右子树压入队尾；同时记录下一层节点个数；
     • 判断当前层是否结束，结束则将弹出的队首元素压入答案中；
   • 返回答案。

四、参考代码

时间复杂度：$\mathrm{O}(n)$【n 是节点数】
空间复杂度：$\mathrm{O}(n)$【最坏情况下，队列的元素占树的一半】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (!root)
            return {};
        vector<int> ans;
        queue<TreeNode*> bfs;
        int cur, next = 0;

        bfs.push(root);
        cur = 1;
        while (bfs.size()) {
            TreeNode* t = bfs.front();
            bfs.pop();
            cur--;

            if (t->left) {
                bfs.push(t->left);
                next++;
            }
            if (t->right) {
                bfs.push(t->right);
                next++;
            }

            if (cur == 0) {
                cur = next;
                next = 0;
                ans.push_back(t->val);
            }
        }

        return ans;
    }
};