199. 二叉树的右视图
199. 二叉树的右视图
🟠 🔖 树
深度优先搜索
广度优先搜索
二叉树
🔗 力扣
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 + 队列实现。
边界情况:如果根节点为
null
,直接返回空数组。层序遍历:
- 使用一个队列来进行二叉树的层序遍历。队列初始时只包含根节点。
- 每次进入新一层时,获取当前队列的长度
len
,表示当前层的节点数。 - 因为我们需要记录每一层的最右侧节点,因此在每层结束时,将当前队列中最后一个节点的值加入到结果数组
res
中。
节点处理:
- 对于每一层的节点,逐一处理队列中的元素:
- 如果当前节点有左子节点,则将左子节点加入队列。
- 如果当前节点有右子节点,则将右子节点加入队列。
- 对于每一层的节点,逐一处理队列中的元素:
更新队列:
- 处理完一层的所有节点后,将队列的前
len
个元素移除(因为它们已经处理过),继续处理下一层。
- 处理完一层的所有节点后,将队列的前
返回结果:
- 当所有层都遍历完成后,返回结果数组
res
,其中包含每层最右侧节点的值。
- 当所有层都遍历完成后,返回结果数组
复杂度分析
- 时间复杂度:
O(n)
,其中n
是二叉树的节点数量,二叉树的每个节点在层序遍历时只会被访问一次。 - 空间复杂度:
O(n)
,因为队列在最坏情况下最多需要存储一半的节点(完全二叉树的最后一层可能有n/2
个节点)。且需要存储最终结果数组,其空间需求为O(L)
,其中L
是二叉树的层数,最多为O(n)
。
代码
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function (root) {
if (!root) return [];
let res = [],
queue = [root];
while (queue.length) {
let len = queue.length;
res.push(queue[len - 1].val);
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);
}
queue = queue.slice(len);
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
116 | 填充每个节点的下一个右侧节点指针 | [✓] | 树 深度优先搜索 广度优先搜索 2+ | 🟠 | 🀄️ 🔗 |
545 | 二叉树的边界 🔒 | 树 深度优先搜索 二叉树 | 🟠 | 🀄️ 🔗 |