###### tags: `Leetcode` `medium` `tree` `bfs` `dfs` `python` `c++`

# 199. Binary Tree Right Side View

## [題目連結:] https://leetcode.com/problems/binary-tree-right-side-view/description/

## 題目:
Given the ```root``` of 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.


## 解題想法:
* 題目為，要求回傳每層中最右邊的node.val

* bfs拜訪每一層，紀錄該層的所有node
* 將該層最後一個node加入最終res

* 同概念題目:[102. Binary Tree Level Order Traversal](/uzzm6rKYT0iLgackHNRl5A)

## Python:

class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
            
class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res=[]
        stack=[root]
        while stack:
            curLevel=[] #此層node
            nextLevel=[] #裝下層
            for node in stack:
                curLevel.append(node.val)
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            res.append(curLevel[-1])
            stack=nextLevel
        return res

if __name__=='__main__':   
    root = TreeNode(1)
    root.insertLeft(2)
    root.insertRight(3)
    root.left.insertRight(5)
    root.left.right.insertRight(6)
    root.right.insertRight(4)
    print("Original: ",end='')
    root.printTree() 

    result=Solution()
    ans = result.rightSideView(root)
    print("the right node: ",ans) 
    #Original: [1, 2, 3, 5, 4, 6]
    #the right node: [1, 3, 4, 6]

## Python:
* 用defaultdict紀錄

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return
        #dfs
        if not root:
            return []
        ans = defaultdict(list)
        map = [ {"level":0, "node":root }]
        while map:
            #取最後 則一定先取到right的
            cur_node = map.pop()
            root=cur_node["node"]
            ans[cur_node["level"]].append(root.val)
            if root.left:
                map.append({"level":cur_node["level"]+1, "node":root.left})
            if root.right:
                map.append({"level":cur_node["level"]+1, "node":root.right})
        return [ ans[i][0] for i in ans]

## C++:
* 因為stack、queue沒有clear功能
* 所以**判斷當前層的node數量進行pop()**
* queue<TreeNode*> curQue;
* int n=curQue.size();
* for (int i=0; i<n; i++)
* root=curQue.front(); curQue.pop();

#include<bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr){}
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left!=nullptr)
        InsertLeft(tmp->left,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->left=new_data;
    }
}

void InsertRight(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->right!=nullptr)
        InsertRight(tmp->right,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->right=new_data;
    }
}

void PrintTree(TreeNode *root){
    TreeNode *tmp=root;
    queue<TreeNode*> que;
    vector<int> res;
    que.push(root);
    while (!que.empty()){
        TreeNode *root=que.front(); que.pop();
        res.push_back(root->val);
        if (root->left)
            que.push(root->left);
        if (root->right)
            que.push(root->right);
    }
    for (auto val: res){
        cout<<val<<" ";
    }
    cout<<endl;
}

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> curQue;
        curQue.push(root);
        vector<int> res;
        if (root==nullptr)
            return res;
        while (!curQue.empty()){
            int n=curQue.size();
            for (int i=0; i<n; i++){
                root=curQue.front(); curQue.pop();
                if (root->left)
                    curQue.push(root->left);
                if (root->right)
                    curQue.push(root->right);
            }
            res.push_back(root->val);
        }
        return res;
    }
};

int main(){
    TreeNode *root=new TreeNode(1);
    InsertLeft(root,2);
    InsertRight(root,3);
    InsertRight(root->left,5);
    InsertRight(root->right,4);
    PrintTree(root);
    Solution res;

    vector<int> ans=res.rightSideView(root);
    for (auto val:ans){
        cout<<val<<" ";
    }
    cout<<endl;
    return 0;
}