二叉树的右视图(力扣 199)Java广度优先遍历
2023-03-14 22:54:54 时间
一、题目描述
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
提示:
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100
二、思路讲解
按层遍历二叉树,将每层最后一个节点的值添加进列表中。返回列表即可。
按层遍历二叉树的代码参考我之前的博客:二叉树的层序遍历 Java广度优先搜索
三、Java代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> list = new ArrayList<>(); if(root==null){ return list; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ //按层遍历二叉树 int n = queue.size(); TreeNode node = null; for(int i=0; i<n; i++){ node = queue.poll(); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } if(node!=null){ //把每一层末尾的节点值放到list中 list.add(node.val); } } return list; } }
四、时空复杂度分析
时间复杂度: O(N)
空间复杂度: O(N)
相关文章
- Java要抛弃祖宗的基业,Java程序员危险了!
- 十大 Java 语言特性
- JVM 三色标记算法,原来是这么回事!
- 聊聊 Spring 事务控制策略以及 @Transactional 失效问题避坑
- 写给 Java 程序员的前端 Promise 教程
- 写给 Java 程序员的前端 Promise 教程,你学会了吗?
- Java 中为什么不全部使用 Static 方法?
- Java 池化技术你了解多少?
- Java 服务 Docker 容器化优秀实践
- Spring Boot + EasyExcel导入导出,简直太好用了!
- 我们一起聊聊 Java 内存泄漏
- CentOS 下安装 Docker 极简教程
- JDK 19 功能集冻结:Java 19 只有七个新特性
- 关于 CMS 垃圾回收器,你真的懂了吗?
- 为什么会有这么多编程语言?
- 改善Java代码的八个建议
- 接口流量突增,如何做好性能优化?
- Java 以编程方式创建JAR文件
- POJO、Java Bean是如何定义的
- Spring 的 Bean 明明设置了 Scope 为 Prototype,为什么还是只能获取到单例对象?