牛客网NC15二叉树的层次遍历
2024-09-03 20:58:43
题目
给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)
例如:
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]
示例2
输入
复制
{1,2,3,4,#,#,5}
返回值
复制
[[1],[2,3],[4,5]]
分析
使用一个队列存放二叉树节点,每次向队列中添加非空节点,从根节点开始加入,将队列中的节点的值取出放入ArrayList中,如果当前节点的左右子节点都不为空,也将放入队列中,依次进行遍历。放入之前需要将当前节点从队列中移除,队列中始终是本层的节点。
代码
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(root==null){
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//根节点入队
queue.offer(root);
while(!queue.isEmpty()){
//存放每层节点个数
ArrayList<Integer> floor = new ArrayList<Integer>();
int len = queue.size();
for(int i=0;i<len;i++){
// 当前节点出队
TreeNode node = queue.poll();
//添加到本层的集合中
floor.add(node.val);
//下层节点入队
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
//将本层节点的值添加到结果集
result.add(floor);
}
return result;
}
}
最新文章
- Java名字的由来
- [翻译] ORMLite document -- How to Use Part (二)
- 2015 年最受 Linux 爱好者欢迎的软硬件大盘点
- STM32之USART库函数USART_SendData的bug
- Input对象的type类型
- AutoFac使用~IOC容器(DIP,IOC,DI)
- SqlServer常用语句参考
- K最近邻
- HTML--3css样式表
- Sqli-labs less 60
- JavaScript之表格过滤器
- Codeforces Round #311 (Div. 2) D. Vitaly and Cycle 奇环
- Git fetch和git pull的区别(转)
- poj 2220 Sumsets
- linux文件属性权限相关
- 利用if else 求已发奖金总数
- sublime2/3自总结经常使用快捷键(2的居多)
- 富文本编辑器UEditor自定义工具栏(二、插入图片、音频、视频个性化功能按钮和弹层及自定义分页符)
- pyqt5 QGraphicsView颜色动画问题(不兼容,运行不了动画)
- git命令设置
热门文章
- 题解-洛谷P5410 【模板】扩展 KMP(Z 函数)
- NPM相关知识点
- 阿里云,批量删除oss所有的bucket
- HBase删除数据
- [日常摸鱼]Luogu2878 [USACO07JAN]Protecting the Flowers
- 题解 P1579 【哥德巴赫猜想(升级版)】
- 是的,你没看错!Python可以实现自动化办公
- 网站开发学习Python实现-Django项目部署-介绍(6.2.1)
- $$ PHP 的含义
- 卡尔曼滤波学习笔记1-Matlab模拟温度例子--代码比较乱,还需优化