199. 二叉树的右视图
一句话套路BFS 每层最后一个结点
题目描述
给定一个二叉树的 根节点 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
思路
时间
O(n)空间
O(宽度)思路
层序遍历,每层取最后一个。
也可用 DFS(根->右->左 的顺序,第一次到达某深度时记录),两种写法都是高频追问点。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0199 {
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
int sz = (int)q.size();
for (int i = 0; i < sz; ++i) {
TreeNode* cur = q.front();
q.pop();
if (i == sz - 1) ans.push_back(cur->val); // 本层最右
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0199::Solution s;
TreeNode* a = buildTree({1, 2, 3, nullopt, 5, nullopt, 4});
CHECK_EQ(s.rightSideView(a), vector<int>{1, 3, 4});
freeTree(a);
TreeNode* b = buildTree({1, 2, 3, nullopt, 5}); // 右侧缺,取到 5
CHECK_EQ(s.rightSideView(b), vector<int>{1, 3, 5});
freeTree(b);
CHECK_EQ(s.rightSideView(nullptr), vector<int>{});