32-Ⅰ 从上到下打印二叉树

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

解题思路：
从上至下按层打印，明显是二叉树的层序遍历，可以借助队列来实现。

代码：

public int[] levelOrder(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> queue = new LinkedList<>();
    if (root != null) {
        queue.offer(root);
    }
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    int[] arr = new int[ans.size()];
    for (int i = 0; i < ans.size(); i++) {
        arr[i] = ans.get(i);
    }
    return arr;
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为二叉树的节点总数。
• 空间复杂度$O(N)$：最差情况下，即当树为平衡二叉树时，最多有 $\frac{2}$ 个树节点同时在 queue 中，使用 $O(N)$ 大小的额外空间。