CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
199. 二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
解法
看到今天leetcode的每日一题，二叉树的右视图！我想起了一个月前字节二面时，面试官问的我这题……哎，当时也写出来了，不过因为后面项目提问部分发挥不好，挂在了二面……
算了，讲正事，这题的话，其实不难，思路也比较简单，就是一个二叉树的从右至左层次遍历（面试的时候，写的是从左至右，然后每次输出最后一个，可能麻烦些），然后每次输出第一个。我的写法如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if(root == nullptr) return ans;
queue<pair<TreeNode*,int>> q;
int cnt = 0;
q.push(make_pair(root,1));
while(!q.empty()){
pair<TreeNode*,int> cur = q.front();
q.pop();
if(cur.first == nullptr) continue;
if(cur.second > cnt){
ans.push_back(cur.first->val);
cnt++;
}
q.push(make_pair(cur.first->right,cur.second+1));
q.push(make_pair(cur.first->left,cur.second+1));
}
return ans;
}
};
然后，过了之后发现貌似内存消耗不小，然后去评论区逛了逛，发现可以这么写：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int size = q.size();
res.push_back(q.front()->val);
while (size--)
{
TreeNode* temp = q.front();
q.pop();
if (temp->right) q.push(temp->right);
if (temp->left) q.push(temp->left);
}
}
return res;
};
上面做法的内存消耗就小多了，不必每个节点都保存一个多余的层次信息，值得学习！