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

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

问题描述

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

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

 3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

提示:

  • 节点总数 <= 1000

解题思路

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

代码实现

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }

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

        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < k; i++){
                TreeNode t = queue.poll();
                tmp.add(t.val);
                if(t.left != null) queue.add(t.left);
                if(t.right != null) queue.add(t.right);
            }
            res.add(tmp);
        }

        return res;
    }
}

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

发表回复

后才能评论

评论(1)

  • 优秀市民 普通 2022年11月1日 下午4:12
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root != null) 
                queue.add(root);
            while(!queue.isEmpty()){
                List<Integer> tmp = new ArrayList<>();
                for(int i = queue.size(); i > 0; i--){
                    TreeNode node = queue.poll();
                    tmp.add(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                }
                res.add(tmp);
            }
            return res;
    
        }
    }
    

    时间复杂度on
    与上一题基本类似,采用BFS的方法按层打印,这里的每层打印到一行可以将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推即可分为多行打印,加一个临时列表,然后循环,循环次数是队列的长度,将每一层的数据存入临时列表后然后循环结束,将这一层的再放入res