目录
- 1. 题目
- 2. 解题思路
- 3. 数据类型功能函数总结
- 4. java代码
1. 题目
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
节点总数 <= 1000
链接：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(;
}
}