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

1. 题目

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

2. 描述

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

3. 实现方法

3.1 方法 1

3.1.1 思路

1. 判断根节点是否为 null，是则直接输出 []
2. 然后用一个列表 list 用于存放二叉树层序遍历结果，同时用一个队列 queue 来存放二叉树层序遍历的节点；
3. 只要队列 queue 不为空，则每次将队尾元素出队并存入 list
4. 然后对左右子节点进入入队处理
5. 最后将列表 list 转换为数组返回即可
6. 主要进行出入队操作，时间复杂度为

O(n)

，然后还有将列表转换为数组，时间复杂度为

O(n)

，所以最终时间复杂度仍为

O(n)

；

3.1.2 实现

代码语言：javascript复制

public int[] levelOrder(TreeNode root) {
    // 队列为空，输出 []
    if (root == null) {
        return new int[0];
    }

    // 列表用于存放最终结果
    ArrayList<Integer> list = new ArrayList<>();
    // 队列用于存放树的顺序遍历
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 根节点出队，并将其加入列表
        TreeNode node = queue.poll();
        list.add(node.val);

        // 处理左子节点
        if (node.left != null) {
            queue.add(node.left);
        }

        // 处理右子节点
        if (node.right != null) {
            queue.add(node.right);
        }
    }

    // 将列表转换为数组
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i  ) {
        res[i] = list.get(i);
    }

    return res;
}

二叉树 编程算法

0 人点赞