199. 二叉树的右视图

1. 题目描述

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

2. 实现思路

对于二叉树的题目，通常会使用深度优先遍历（DFS）或者广度优先遍历（BFS）来遍历。下面就来用这两种方法来解决这个问题。

DFS：

• 设置一个level，来保存当前遍历的二叉树的层级，初始值为0
• 由于我们需要返回的是右视图的节点值，所以先遍历右节点的值，将右节点保存在结果数组中
• 然后遍历左节点
• 当结果数组的长度和二叉树当前的层级相同时，就将当前的节点值保存
• 重复上述步骤，直至遍历完二叉树的所有节点

BFS：
使用广度优先遍历来遍历二叉树，这就相当于二叉树的层序遍历，对于每一层的遍历结果，取最后一个即可，这里我们使用队列来处理。

• 初始化一个队列，将根节点加入到队列中
• 当队列不为空的时候，就将队列的元素出队，将最后一个元素加入到结果数组中
• 在元素出队列的时候，将元素的左右子节点分别加入到队列中
• 重复上面的第二三步，直至队列为空

  3. 代码实现

  DFS： ```javascript /**
  • Definition for a binary tree node.
  • function TreeNode(val) {
  • this.val = val;
  • this.left = this.right = null;
  • } / /*
  • @param {TreeNode} root
  • @return {number[]} */ var rightSideView = function(root) { if(!root) return [] let res = [] dfs(root, 0, res) return res };

function dfs(root, level, res){ if(root){ if(res.length === level){ res.push(root.val) }

    dfs(root.right, level+1, res)
    dfs(root.left, level+1, res)
}

}

**BFS：**
```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if(!root) return []
    let res = []
    let queue = [root]
    while(queue.length > 0){
        let len = queue.length
        while(len){
            let node = queue.shift()
            if(len === 1){
                res.push(node.val)
            }
            if(node.left){
                queue.push(node.left)
            }
            if(node.right){
                queue.push(node.right)
            }
            len--
        }
    }
    return res
};

4. 提交结果

DFS：

BFS：