199. 二叉树的右视图

文章目录

• • 题目
  • 代码
  • 原理图
  • 原理解释
  • 结束

题目

199. 二叉树的右视图 给定一个二叉树的 根节点 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

代码

/**
* 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) {
vector<int> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* rightNode=NULL;
int levelSize=q.size();
for(int i=0;i<levelSize;i++)
{
TreeNode* cur=q.front();
q.pop();
if(cur)
{
rightNode=cur;
q.push(cur->left);
q.push(cur->right);
}
}
if(rightNode)
{
res.push_back(rightNode->val);
}
}
return res;
}
};

原理图

原理解释

方法： 该代码采用二叉树层序遍历（广度优先搜索，BFS） 实现二叉树的右视图，核心思路是按层遍历二叉树，记录每一层的最后一个非空节点值，这些值按层拼接即为右视图结果。 层序遍历（BFS）的分层处理是关键：通过levelSize固定每一层的节点数，确保内层循环仅处理当前层节点；通过 “从左到右遍历 + 持续更新rightNode”，自然得到当前层的最后一个非空节点（右视图节点），最终拼接所有层的结果即为答案。

结束