199. Binary Tree Right Side View

🟠   🔖  树 深度优先搜索 广度优先搜索 二叉树  🔗 LeetCode

题目

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.

Example 1:

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: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

题目大意

从右边看一个树，输出看到的数字，注意有遮挡。

解题思路

这一题是按层序遍历的变种题，按照层序把每层的元素都遍历出来，然后依次取每一层的最右边的元素即可，用 BFS + 队列实现。

代码

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
  let res = [];
  if (!root) return res;
  let queue = [root];
  while (queue.length) {
    let temp = [];
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      if (queue[i].left) queue.push(queue[i].left);
      if (queue[i].right) queue.push(queue[i].right);
      temp.push(queue[i].val);
    }
    queue = queue.slice(len);
    res.push(temp);
  }
  return res.map((i) => i[i.length - 1]);
};

相关题目

相关题目

• 116. 填充每个节点的下一个右侧节点指针
• 🔒 Boundary of Binary Tree
• 102. 二叉树的层序遍历
• 107. 二叉树的层序遍历 II

- [116. 填充每个节点的下一个右侧节点指针](./0116.md)
- [🔒 Boundary of Binary Tree](https://leetcode.com/problems/boundary-of-binary-tree)
- [102. 二叉树的层序遍历](./0102.md)
- [107. 二叉树的层序遍历 II](./0107.md)