二叉树的右侧视图
# 📃 题目描述
题目链接:
- 剑指 Offer II 046. 二叉树的右侧视图 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 199. 二叉树的右视图 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个二叉树的 根节点 root
,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
# 🔔 解题思路
# 层序遍历(BFS)
和上道题 剑指 Offer II 044. 二叉树每层的最大值 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 基本没差,层序遍历,记录每层的最后一个节点即可(if (i == size - 1)
)
class Solution {
public List<Integer> rightSideView(TreeNode root) {
// 记录每一层的最右边节点
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
// 遍历当前层
for (int i = 0; i < size; i ++) {
TreeNode cur = queue.poll();
// 当前层最右边节点
if (i == size - 1) {
res.add(cur.val);
}
// 左右孩子入队
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
return res;
}
}
# DFS
思路: 我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问,就可以保证每层都是最先访问最右边的节点的。
(与先序遍历 「根结点 -> 左子树 -> 右子树」 正好相反,先序遍历每层最先访问的是最左边的节点)
- 时间复杂度: O(N),每个节点都访问了 1 次
- 空间复杂度: O(N),因为这不是一棵平衡二叉树,二叉树的深度最少是 logN, 最坏的情况下会退化成一条链表,深度就是 N,因此递归时使用的栈空间是 O(N) 的
class Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
if (root == null) {
return res;
}
dfs(root, 0);
}
// 遍历(根右左) root 树,当前深度为 depth
private void dfs(TreeNode root, int depth) {
if (root == null) {
return ;
}
// 如果当前节点所在深度还没有出现在res里,说明在该深度下当前节点是第一个被访问的节点,因此将当前节点加入res中。
if (depth == res.size()) {
res.add(root.val);
}
dfs(root.right);
dfs(root.left);
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10