二叉树的右视图

Tips

题目类型: Tree

题目

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

示例

输入: [1,2,3,null,5,null,4]

输出: [1, 3, 4]

解释:

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

题解

思路很简单, 就是层序遍历. 并先将右节点入队, 再入队左节点, 这样就保证了每层的队头元素就是最右节点.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
  const res = []
  if (!root) return res
  const queue = [root]

  while (queue.length > 0) {
    // 每层的队头元素就是最右节点
    res.push(queue[0].val)

    const n = queue.length
    for (let i = 0; i < n; i++) {
      const node = queue.shift()

      if (node.right) queue.push(node.right)
      if (node.left) queue.push(node.left)
    }
  }

  return res
}