LeetCode Q199: Binary Tree Right Side View

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="" 4="" 5="" pre="">



You should return [1, 3, 4].



Solution:

	/**
	* 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==NULL)
	return res;
	queue<TreeNode*> Q;
	int last=0;
	int cur=0;
	Q.push(root);
	last = 1;
	while(!Q.empty()){
	TreeNode* frontNode=Q.front();
	Q.pop();
	if(last==1)
	res.push_back(frontNode->val);
	if(frontNode->left!=NULL){
	Q.push(frontNode->left);
	cur++;
	}
	if(frontNode->right!=NULL){
	Q.push(frontNode->right);
	cur++;
	}
	last--;
	if(last==0){
	last=cur;
	cur=0;
	}
	}
	return res;
	}
	};

view raw Q199BinaryTreeRightSideView.cpp hosted with ❤ by GitHub

Rnd3

	/**
	* 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:
	void helper(TreeNode* root, unordered_map<int, int>& myMap, int level){
	if(root==NULL)
	return;
	auto it = myMap.find(level);
	if(it==myMap.end()){
	myMap[level]=root->val;
	}
	helper(root->right, myMap, level+1);
	helper(root->left, myMap, level+1);
	}
	vector<int> rightSideView(TreeNode* root) {
	vector<int> res;
	if(root==NULL)
	return res;
	unordered_map<int, int> myMap;
	helper(root, myMap, 0);
	int i=0;
	auto it = myMap.find(i);
	while(it!=myMap.end()){
	res.push_back(it->second);
	it = myMap.find(++i);
	}
	return res;
	}
	};

view raw Q199Rnd3.cpp hosted with ❤ by GitHub