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

本问题对应的 leetcode 原文链接:剑指 Offer 32 – I. 从上到下打印二叉树
本次对应打卡任务:【二叉树专题】剑指 Offer 32 – I. 从上到下打印二叉树

问题描述

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

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

    3
   / \
  9  20
    /  \
   15   7

返回:

[3,9,20,15,7]

提示:

  • 节点总数 <= 1000

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }

        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();

        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            res.add(t.val);
            if(t.left != null) queue.add(t.left);
            if(t.right != null) queue.add(t.right);
        }

        int[] arr = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            arr[i] = res.get(i);
        }

        return arr;

    }
}

时间复杂度:O(n)
额外空间复杂度:容器里最对存放 1/2 的节点,故为 O(n)

发表回复

后才能评论