好久没有刷leetcode了，要继续了。。
今天第一题。
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
一看到就觉得是层次遍历，而且每层的最后一个结点会保存下来。
C++实现代码：
#include<iostream>
#include<new>
#include<vector>
#include<queue>
using namespace std;
//Definition for binary tree
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) {
if(root==NULL)
return vector<int>();
vector<int> res;
queue<TreeNode*> q;
q.push(root);
int cur=1;
while(!q.empty())
{
int rcur=0;
while(cur)
{
TreeNode *tmp=q.front();
q.pop();
cur--;
if(cur==0)
res.push_back(tmp->val);
if(tmp->left)
{
q.push(tmp->left);
rcur++;
}
if(tmp->right)
{
q.push(tmp->right);
rcur++;
}
}
cur=rcur;
}
return res;
}
void createTree(TreeNode *&root)
{
int i;
cin>>i;
if(i!=0)
{
root=new TreeNode(i);
if(root==NULL)
return;
createTree(root->left);
createTree(root->right);
}
}
};
int main()
{
Solution s;
TreeNode *root;
s.createTree(root);
vector<int> vec;
vec=s.rightSideView(root);
for(auto a:vec)
cout<<a<<" ";
cout<<endl;
}
