从上到下打印二叉树

问题描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回：[3,9,20,15,7]

问题分析

这个是一个比较典型的二叉树广度优先搜索：BSF，主要是利用队列的方式来作为辅助的数据结构；

1. 获取队列大小，当前队列的大小表示该层节点个数；
2. 调用queue的poll方法逐个打印，并把改节点的左右孩子添加到队列中；
3. 获取最终的数组数据；

代码实现

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }
        Queue<TreeNode> que = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        que.add(root);
        while(!que.isEmpty()){
            //当前层级节点的个数
            int size = que.size();
            for(int i=0; i < size; i++){
                TreeNode node = que.poll();
                list.add(node.val);
                if(node.left != null){
                    que.add(node.left);
                }
                if(node.right != null){
                    que.add(node.right);
                }
            }
        }
        int[] result = new int[list.size()];
        for(int j=0; j<list.size(); j++){
            result[j] = list.get(j);
        }
        return result;
    }
}