剑指 Offer 32 - I. 从上到下打印二叉树(java解题)

时间:2023-02-11 20:08:15

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
 
例如:
给定二叉树: [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();
    }
}