199. 二叉树的右视图
3 min
题目
解法：层序遍历
思路
第一段：使用广度优先搜索（BFS）进行层序遍历，每层取最后一个节点作为右视图节点。
第二段：BFS 能保证按层访问节点，当遍历到每层的最后一个节点时，该节点即为从右侧视角能看到的节点，因为右侧视角看到的是每层最靠右的节点。这种方法通过队列的先进先出特性，确保每层节点按从左到右的顺序处理，从而正确捕获每层的最右节点。
第三段：
- Step 1: 初始化队列并将根节点入队
- Step 2: 循环处理每一层，记录当前层节点数
- Step 3: 遍历当前层所有节点，将最后一个节点的值加入结果
- Step 4: 将子节点加入队列，继续下一层遍历
复杂度
- 时间复杂度: ，其中 n 为节点数，每个节点仅被访问一次
- 空间复杂度: ，最坏情况下队列需要存储所有节点
代码
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
deque<TreeNode*> dq;
dq.push_back(root);
while (!dq.empty()) {
int size = dq.size();
for (int i = 0; i < size; i++) {
TreeNode* node = dq.front();
dq.pop_front();
if (i == size - 1) {
ans.push_back(node->val);
}
if (node->left) {
dq.push_back(node->left);
}
if (node->right) {
dq.push_back(node->right);
}
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
deque<TreeNode*> dq;
dq.push_back(root);
while (!dq.empty()) {
int size = dq.size();
for (int i = 0; i < size; i++) {
TreeNode* node = dq.front();
dq.pop_front();
if (i == size - 1) {
ans.push_back(node->val);
}
if (node->left) {
dq.push_back(node->left);
}
if (node->right) {
dq.push_back(node->right);
}
}
}
return ans;
}
};