# 199. Binary Tree Right Side View

### Leetcode

<https://leetcode.com/problems/binary-tree-right-side-view/>

### 題目

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*.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/14/tree.jpg)

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

**Example 2:**

```
Input: root = [1,null,3]
Output: [1,3]
```

**Example 3:**

```
Input: root = []
Output: []
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

用 `level` 記錄每層的層數，由右邊先行遍歷，如此一來只要第一次遍歷到的節點且原本在相對應的 `level` 上沒有數值，就是同層最右邊的節點

```
var rightSideView = function(root) {
    if(!root) return [];
    
    const res = [];
    const queue = [root];
    
    let level = 0;
    while(queue.length) {
        const len = queue.length;
        for(let i=0; i<len; i++) {
            const node = queue.shift();
            if (res[level] === undefined) {
                res[level] = node.val;
            }
            if(node.right) queue.push(node.right);
            if(node.left) queue.push(node.left);
        }
        level++;
    }
    
    return res;
};
```

Runtime: 100 ms, faster than 31.84% of JavaScript online submissions for Binary Tree Right Side View.

Memory Usage: 43.9 MB, less than 57.38% of JavaScript online submissions for Binary Tree Right Side View.

* **方法二**

DFS

```
var rightSideView = function(root) {
    const res = [];
    const dfs = (node, level) => {
        if (!node) return;
        if (res[level] === undefined) {
            res[level] = node.val;
        };
        dfs(node.right, level+1);
        dfs(node.left, level+1);
    }
    
    dfs(root, 0);
    return res;
};
```

Runtime: 87 ms, faster than 52.33% of JavaScript online submissions for Binary Tree Right Side View.

Memory Usage: 43.8 MB, less than 67.93% of JavaScript online submissions for Binary Tree Right Side View.
