当前位置：
  1. 首页
  2. 剑指offer最优解
  3. 正文

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

剑指offer最优解 0 73

本问题对应的 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


剑指offer最优解系列教程