33_从上到下打印二叉树I

要求：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
思路： 使用二叉树的广度遍历BFS。(广度（层次遍历）优先遍历用队列，深度优先遍历用栈)
广搜的套路就是用一个队列保存将要搜索的这一层的元素，然后逐个搜索；
1、将第一个元素加入队列
2、队列不为空时取队首元素
3、将下一层元素加入队尾
4、调到第二步，直到队列为空

public class L33_PrintFromTopToBottom {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode0 root){
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode0> qu = new LinkedList<>();
        if(root!=null){
            qu.add(root);
        }else{
            return list;
        }
        while(!qu.isEmpty()){
            TreeNode0 temp = qu.poll();
            list.add(temp.value);
            if(temp.left!=null){
                qu.add(temp.left);
            }
            if(temp.right!=null){
                qu.add(temp.right);
            }
        }
        return list;
    }
}

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。
空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 O(N) 大小的额外空间。