剑指 Offer 32 - I. 从上到下打印二叉树(java解题)
2023-03-20 15:21:25 时间
1. 题目
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回:
[3,9,20,15,7]
提示:
节点总数 <= 1000
作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/9ackoe/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
2. 解题思路
题目要求打印节点,且是按照每层从左往右的顺序打印,实际上是需要实现层次遍历。
层次遍历需要用到队列这个数据结构,在这里我们使用LinkedList
数据结构模拟队列。
基本的求解过程即:
- 创建队列,将根节点放入队列中;
- 当队列非空时,取出队列的首个节点,将节点值存入结果数组中,同时将该节点的左右子树节点放入队列中;
要注意两点:
- 结果数组的实现:这是一个不定长的int型数组,因此,先使用
ArrayList<Integer>
实现不定长数组,然后将ArrayList<Integer>
转化为int[]
,如何转化可参考此篇博文 - 插入队列之前,需要先对节点进行非空判断,如果一个空节点插入队列中,会占据一个位置,但是实际上没有数据,导致结果数组中存在异常值,且可能导致队列永远不为空。
3. 数据类型功能函数总结
//LinkedList
LinkedList<E> listname=new LinkedList<E>();//初始化
LinkedList.add(elment);//在链表尾部添加元素
LinkedList.removeFirst();//取出链表头部元素
LinkedList.size();//获取元素个数
//ArrayList
ArrayList<E> listname=new ArrayList<E>();//初始化
ArrayList.add(elment);//在数组最后插入元素
ArrayList.stream().mapToInt(Integer::valueOf).toArray();//ArrayList<Integer>转为int[]
ArrayList.toArray();//Arraylist转为数组,适用于String--char[]
//int[]
arrayname=new ElementType[size];//创建大小为size的数组,元素类型为ElementType
4. java代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//树节点的遍历问题——层次遍历--队列
class Solution {
public int[] levelOrder(TreeNode root) {
ArrayList<Integer> result_list = new ArrayList<Integer>();//结果数组
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//队列
if(root!=null){
queue.add(root);
}
while(queue.size()!=0){
TreeNode temp=queue.removeFirst();
if(temp.left!=null){
queue.add(temp.left);
}
if(temp.right!=null){
queue.add(temp.right);
}
result_list.add(temp.val);
}
return result_list.stream().mapToInt(Integer::valueOf).toArray();
}
}
相关文章
- 深入探讨Java中的异常与错误处理
- 研究学习Kotlin的一些方法
- 数据显示Java热度持续下落,日子屈指可数?
- 2017年5月编程语言排行榜:Java与C语言优势正开始缩小
- Java多线程之内置锁与显示锁
- Java线程池的理论与实践
- 白话阿里巴巴Java开发手册(编程规约)
- 关于Java你不知道的十件事
- Java服务化系统线上应急和技术攻关,你必须掌握的Linux命令
- Java实现高斯模糊和图像的空间卷积
- Java阻塞队列实现原理分析
- NPM使用技巧
- Node.js对Java开发者而言是什么?
- Java反射机制应用实践
- 理解RxJava中的Single和Completable
- 2017年你不能错过的Java类库
- 大规模集群下的Hadoop NameNode
- 从源码解密Spark内存管理
- 2017年3月编程语言排行榜:Swift首次进入前十
- JVM热点技术:Java类的加载机制