剑指 Offer 32 – I. 从上到下打印二叉树（java解题）

目录

• 1. 题目
• 2. 解题思路
• 3. 数据类型功能函数总结
• 4. java代码

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数据结构模拟队列。
基本的求解过程即：

1. 创建队列，将根节点放入队列中；
2. 当队列非空时，取出队列的首个节点，将节点值存入结果数组中，同时将该节点的左右子树节点放入队列中；

要注意两点：

1. 结果数组的实现：这是一个不定长的int型数组，因此，先使用ArrayList<Integer>实现不定长数组，然后将ArrayList<Integer>转化为int[]，如何转化可参考此篇博文
2. 插入队列之前，需要先对节点进行非空判断，如果一个空节点插入队列中，会占据一个位置，但是实际上没有数据，导致结果数组中存在异常值，且可能导致队列永远不为空。

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();     } }