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

Lin2J
2021-07-21 / 0 评论 / 89 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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)$ 大小的额外空间。