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

题目

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

题解

队列

• 初始化队列queue和结果数组res，从二叉树根节点3开始
• 先将3推入到队列queue中，看3有没有左子树和右子树
• 有的话，将3从队列queue中取出，放入结果数组res的第一位，此时res = []int{3}
• 访问3的左子树节点9，将9推入到队列queue中
• 此时看9有没有左子树和右子树，没有，将9从队列queue中取出放入结果数组res中，此时res = []int{3,9}
• 访问3的右子树节点20，将20推入到队列queue中
• 此时看20有没有左子树和右子树，有，将左子树15推入队列queue中
• 看15有没有左子树和右子树，没有，将队列中的20，15依次取出放入结果数组res，此时res = []int{3,9,20,15}
• 访问20的右子树7，发现7没有左子树和右子树，将7推入进队列queue中，然后取出放入res，此时res = []int{3,9,20,15,7}

//Java
/**
 * 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) {
        // 根节点为空的情况返回空数组
        if(root == null) return new int[0];

        // 生成一个队列，用来保存节点
        Queue<TreeNode> queue = new LinkedList<>();

        // 生成一个list，用来保存输出的节点
        List<Integer> list = new ArrayList<>();

        // 首先让根节点入队
        queue.add(root);

        // 遍历队列，直到队列为空
        while (!queue.isEmpty()) {
            // 获取队列的头部元素
            TreeNode node = queue.poll();
            // 把节点值存放到list中
            list.add(node.val);
            // 判断该节点是否有左右子节点

            // 如果左子节点有值，则把左子节点加入到队列中
            if (node.left != null) {
                queue.add(node.left);
            }
            // 如果右子树有值，则把右子节点加入到队列中
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        // 把list转化为数组
        int[] res = new int[list.size()];
        for (int i = 0;i < list.size();i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}

leetcode-cn执行

执行用时：1 ms, 在所有 Java 提交中击败了97.77%的用户
内存消耗：41.5 MB, 在所有 Java 提交中击败了28.48%的用户