# 199. Binary Tree Right Side View

## problem description

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.

**Example:**

```
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
```

## algorithm thought

找到每一层最右边的节点，简单办法是直接用层次遍历，遍历每一层。跳到下一层的时候，将每一层最后的一个节点push到结果中。

在discuss中看到一个很聪明的办法，直接用改动的先根遍历找到结果，改动的地方就是，访问顺序变为，先根后右再左。每次访问时，判断层次和结果大小的关系。因为是先访问右再左，每一层第一个访问的，肯定是最右边的节点。第一个访问的就直接push到结果。

如果这题是求出最左的节点，按照上面的方法，直接用先根遍历就可以得出结果。

## code

```cpp
//层次遍历的方法
/**
 * 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) {
        queue<TreeNode*> qu;
        TreeNode* tmp=new TreeNode(-1);
        vector<int>res;
        if(root==NULL)
            return res;
        res.push_back(root->val);
        qu.push(root->left);
        qu.push(root->right);
        qu.push(tmp);
        int r;
        while(!qu.empty()){
            TreeNode* t=qu.front();
            qu.pop();
            if(t==NULL){
                continue;
            }
            if(t==tmp){
               // cout<<qu.size()<<' ';
                if(qu.empty())
                    break;
                res.push_back(r);
                qu.push(tmp);
                continue;
            }
            qu.push(t->left);
            qu.push(t->right);
            r=t->val;
        }
        return res;
    }
};

//修改的先根遍历的方法
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        modify_preorder(root,1,res);
        return res;
    }
    void modify_preorder(TreeNode* root,int level,vector<int>&res){
        if(root==nullptr)
            return;
        if(res.size()<level)
            res.push_back(root->val);
        modify_preorder(root->right,level+1,res);
        modify_preorder(root->left,level+1,res);
    }  
};
```

## algorithm analysis

两个算法都是需要将树遍历一遍才能得到答案，时间和空间复杂度都是O(n)。

但是第二中算法在遍历中每次操作的次数明显比第一种少，并且简洁。所以第二种算法更好


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/199.-binary-tree-right-side-view.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.