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

[songyy5517]

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

例如: 给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回：

[3,9,20,15,7]

分析 这道题本质上是考察二叉树的层次遍历。因此，我们可以使用队列来实现。

[songyy5517]

思路：基于队列的BFS

1. 异常处理；
2. 创建队列和列表；
3. 基于队列对二叉树进行广度优先遍历（BFS）/层次遍历；
4. 将列表转换成数组，并返回。

复杂度分析

• 时间复杂度： $O(N)$ ，对树中的所有节点进行遍历， $N$ 为树的总节点数。
• 空间复杂度： $O(N)$ ，列表最大容量为 $N$ ，队列的最大容量为 $\frac{N + 1}{2}$ （满树的最后一层）。

[songyy5517]

/**
 * 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) {
        // 1. 异常处理
        if (root == null)
            return new int[0];

        // 2. 创建队列和列表
        ArrayList<Integer> temp = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();    // !2023/3/9  用LinkedList创建队列
        queue.add(root);

        // 3. 基于队列对二叉树进行广度优先搜索 (BFS)
        while(!queue.isEmpty()){
            TreeNode cur = queue.remove();    // !2023/3/9  不能用pop
            temp.add(cur.val);

            if (cur.left != null)
                queue.add(cur.left);

            if (cur.right != null)
                queue.add(cur.right);
        }

        // 4. 将列表转换成数组，并返回
        int[] res = new int[temp.size()];
        for (int i = 0; i < temp.size(); i++)
            res[i] = temp.get(i);

        return res;
    }
}

[songyy5517]

2023/1/26 2023/1/28

2023/3/9

1. 创建队列 Queue<TreeNode> queue = new LinkedList<TreeNode>();
2. 删除队列中的元素不能用pop queue.remove()

2024/1/27 2024/2/26

• 双端队列保存每行的结果，方便实现顺序的反转。