每日一题(LeetCode)----二叉树-- 二叉树的右视图
每日一题(LeetCode)----二叉树-- 二叉树的右视图
1.题目（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
- 二叉树的节点个数的范围是
2.解题思路
思路一：层序遍历
1.使用一个队列 其中元素的类型为node类型的指针（这里的队列我们用的是c++中封装好的，其实是模板类，我们这里是通过模板类创建了一个对象）和一个结果数组，结果数组用来存最终的结果
2.定义一个变量来记录当前层元素的个数
3.初始时，我们将根节点放入到队列中去，当前层元素个数记为1（提示：每出队列一个元素，那么当前层元素的个数进行-1操作）
4.我们将队列中的首元素出列，并将其不为空的左孩子和右孩子入队，然后当前层元素个数-1，当当前层元素个数变为0时，我们将当前元素放入到我们的结果数组中，并获取下一层元素个数，重复这个操作，直到队列为空结束
5.返回结果数组
3.写出代码
思路一的代码
class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> res;if(root==nullptr){return res;}queue<TreeNode*> qe;int t=0;qe.push(root);t=1;while(!qe.empty()){TreeNode* temp=qe.front();qe.pop();if(temp!=nullptr&&temp->left!=nullptr){qe.push(temp->left);}if(temp!=nullptr&&temp->right!=nullptr){qe.push(temp->right);}t--;if(t==0){t=qe.size();res.push_back(temp->val);}}return res;}
};