(树) 剑指 Offer 32 - II. 从上到下打印二叉树 II ——【Leetcode每日一题】

news/2024/4/21 1:18:39/

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

难度:简单

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

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

    3/ \9  20/  \15   7

返回其层次遍历结果:

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

提示:

  • 节点总数 <= 1000

注意:本题与 102. 二叉树的层序遍历 相同。

💡思路:BFS

这里借助 优先队列 来实现 广度优先遍历

  • 由于需要访问每一层的节点,而且这一层访问才可以访问下一层, 所以另设一个计数变量 cnt 每访问一层,都要先记录此时队列中有多少元素,即为该层有多少个数。
    • 每访问队列中一个元素就就 cnt--
    • cnt 等于 0 时,则该层数据访问完毕。
  • 在结点出队时,如果其左右子结点不为空时,则将子节点入队。
  • 直到 优先队列 为空时结束。

🍁代码:(C++、Java)

C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if(root == nullptr) return ans;queue<TreeNode*> q;q.push(root);while(!q.empty()){int cnt = q.size();vector<int> temp;while(cnt-- > 0){TreeNode* cur = q.front();q.pop();temp.push_back(cur->val);if(cur->left != nullptr) q.push(cur->left);if(cur->right != nullptr) q.push(cur->right);}ans.push_back(temp);}return ans;}
};

Java

/*** 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) {List<List<Integer>> ans = new ArrayList<List<Integer>>();if(root == null) return ans;Queue<TreeNode> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){int cnt = q.size();ArrayList<Integer> temp = new ArrayList<>();while(cnt-- > 0){TreeNode cur = q.poll();temp.add(cur.val);if(cur.left != null) q.add(cur.left);if(cur.right != null) q.add(cur.right);}ans.add(temp);}return ans;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为树上所有节点的个数,每个点进队出队各一次,故渐进时间复杂度为 O ( n ) O(n) O(n)
  • 空间复杂度 O ( n ) O(n) O(n),队列中元素的个数不超过 n 个,故渐进空间复杂度为 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/997770.html

相关文章

云服务器无法远程连接服务

问题 今天刚买了华为的云服务器&#xff0c;通过宝塔安装了对应的基础服务&#xff0c;也在华为云的官网上设置了安全组。此时万事俱备只欠东风&#xff0c;我测试使用sqlyog进行远程连接。原本已经在准备部署项目了&#xff0c;现实给了我重重的一拳。 sqlyog爆2003代码错误&…

《golang设计模式》第一部分·创建型模式-04-抽象工厂模式(Abstract Factory)

文章目录 1. 概述1.1 角色1.2 类图 2. 代码示例2.1 设计2.2 代码2.3 类图 1. 概述 1.1 角色 AbstractFactory&#xff08;抽象工厂&#xff09;&#xff1a;它声明了一组用于创建产品的方法&#xff0c;每一个方法对应一种产品。ConcreteFactory&#xff08;具体工厂&#xf…

微信小程序接入腾讯云天御验证码

腾讯云新一代行为验证码&#xff08;Captcha&#xff09;&#xff0c;基于十道安全防护策略&#xff0c;为网页、APP、小程序开发者打造立体、全面的人机验证。在保护注册登录、活动秒杀、点赞发帖、数据保护等各大场景下业务安全的同时&#xff0c;提供更精细化的用户体验。 …

Vue源码学习 - 虚拟Dom 和 diff算法

目录 前言一、认识虚拟DOM用 JS 对象模拟 DOM 结构用JS对象模拟DOM节点的好处为什么要使用虚拟 DOM 呢&#xff1f;虚拟Dom 和 diff算法的关系 二、认识diff算法diff算法的优化key的作用diff算法 在什么时候执行&#xff1f; 三、深入diff算法源码patch 函数sameVnode 函数patc…

Java源码规则引擎:jvs-rules决策流的自定义权限控制

规则引擎用于管理和执行业务规则。它提供了一个中央化的机制来定义、管理和执行业务规则&#xff0c;以便根据特定条件自动化决策和行为。规则引擎的核心概念是规则。规则由条件和动作组成。条件定义了规则适用的特定情况或规则触发的条件&#xff0c;而动作定义了规则满足时要…

python 统计所有的 仓库 提交者的提交次数

字典去重 YYDS 然后再写入excel 表 yyds #!/bin/env python3 from git.repo import Repo import os import pandas as pdspath "/home/labstation/workqueue/sw" url "git10.0.128.128" date [str(x) for x in range(202307, 202308)] datefmt "%…

【PyQt实现复现框CheckBox】

PyQt实现复现框CheckBox 1 安装环境2 CtrlN&#xff0c;新建Main Window窗口&#xff0c;保存为checkBox.ui文件3 CheckBox的三种状态4 实现通用复选框的选中状态设置用户权限功能 1 安装环境 1&#xff09;Python环境安装PyQt5、PyQt-sip、PyQt5Designer、PyQt5-tools 2&…

【Deepsort】C++版本Deepsort编译(依赖opencv,eigen3)

目录 下载源码安装onnxruntime安装Eigen3编译opencv 下载源码 https://github.com/shaoshengsong/DeepSORT安装onnxruntime 安装方法参考博客 安装Eigen3 当谈及线性代数计算库时&#xff0c;Eigen3是一个强大而受欢迎的选择。Eigen3是一个C模板库&#xff0c;提供了许多用…

ChatGPT的功能与特点

随着人工智能技术的不断发展&#xff0c;ChatGPT作为OpenAI公司开发的基于GPT-3.5架构的大型语言模型&#xff0c;正引领着智能交互的新纪元。ChatGPT的功能与特点使其能够在多个领域展现出惊人的能力&#xff0c;本文将深入探讨ChatGPT的功能与特点&#xff0c;以及它在人工智…

Linux常用命令——dpkg-divert命令

在线Linux命令查询工具 dpkg-divert Debian Linux中创建并管理一个转向列表 补充说明 dpkg-divert命令是Debian Linux中创建并管理一个转向&#xff08;diversion&#xff09;列表&#xff0c;其使得安装文件的默认位置失效的工具。 语法 dpkg-divert(选项)(参数)选项 -…

手撕SpringBoot的自定义启动器

一. 前言 哈喽&#xff0c;大家好&#xff0c;最近金九银十&#xff0c;又有不少小伙伴私信辉哥&#xff0c;说自己在面试时被问到SpringBoot如何自定义启动器&#xff0c;结果自己不知道该怎么回答。那么今天就手把手地带着大家&#xff0c;去看看在SpringBoot中到底该怎么实…

Kafka3.0.0版本——Broker(Zookeeper服务端存储的Kafka相关信息)

目录 一、启动zookeeper集群及kafka集群服务启动1.1、先启动三台zookeeper集群服务&#xff0c;再启动三台kafka集群服务1.2、使用PrettyZoo连接zookeeper客户端工具 二、在zookeeper服务端存储的Kafka相关信息 一、启动zookeeper集群及kafka集群服务启动 1.1、先启动三台zook…

Matlab进阶绘图第24期—悬浮柱状图

悬浮柱状图是一种特殊的柱状图。 与常规柱状图相比&#xff0c;悬浮柱状图可以通过悬浮的矩形展示最小值到最大值的范围&#xff08;或其他范围表达&#xff09;&#xff0c;因此在多个领域得到应用。 本文使用自己制作的Floatingbar小工具进行悬浮柱状图的绘制&#xff0c;先…

Jmeter —— jmeter参数化实现

jmeter参数化 在实际的测试工作中&#xff0c;我们经常需要对多组不同的输入数据&#xff0c;进行同样的测试操作步骤&#xff0c;以验证我们的软件的功能。这种测试方式在业界称为数据驱动测试&#xff0c; 而在实际测试工作中&#xff0c;测试工具中实现不同数据输入的过程称…

k8s概念-深入pod

回到目录 工作负载&#xff08;workloads&#xff09; 工作负载&#xff08;workload&#xff09;是在kubernetes集群中运行的应用程序。无论你的工作负载是单一服务还是多个一同工作的服务构成&#xff0c;在kubernetes中都可以使用pod来运行它 workloads分为pod与control…

【C++】做一个飞机空战小游戏(三)——模块化程序设计

[导读]本系列博文内容链接如下&#xff1a; 【C】做一个飞机空战小游戏(一)——使用getch()函数获得键盘码值 【C】做一个飞机空战小游戏(二)——利用getch()函数实现键盘控制单个字符移动【C】做一个飞机空战小游戏(三)——模块化程设设计 在前两讲当中&#xff0c;介绍了利用…

BIO、NIO、IO多路复用模型详细介绍Java NIO 网络编程

文章目录 前言基本概念BIO过程NIO过程IO多路复用过程Java NIO编程Java NIO 核心概念Java NIO 示例 总结 前言 上文介绍了网络编程的基础知识&#xff0c;并基于 Java 编写了 BIO 的网络编程。我们知道 BIO 模型是存在巨大问题的&#xff0c;比如 C10K 问题&#xff0c;其本质就…

iMacros WebBrowser Component for .NET

iMacros WebBrowser Component for .NET 在几分钟内实现应用程序自动化 快速轻松地将iMacro集成到您的应用程序中。不需要单独的安装程序。 无缝集成 iMacros与您的.NET应用程序无缝集成&#xff0c;作为Microsoft WebBrowser控件的替代品。它甚至可以用作每个.NET应用程序中的…

kaggle新赛:RSNA 2023 腹部创伤检测大赛赛题解析(CV)

赛题名称&#xff1a;RSNA 2023 Abdominal Trauma Detection 赛题链接&#xff1a; https://www.kaggle.com/competitions/rsna-2023-abdominal-trauma-detection 赛题背景 腹部钝力创伤是最常见的创伤性损伤类型之一&#xff0c;最常见的原因是机动车事故。腹部创伤可能导致…

C# Blazor 学习笔记(3):路由管理

文章目录 前言路由管理App.razor设置登录页面设置空布局 前言 我们知道使用Blazor的官方模板&#xff0c;我们会自动得到一个拥有侧边栏的布局页面。但是我们发现我们所有新建的页面都有侧边栏。有时候我们需要跳出这个布局&#xff0c;比如我要做登录页面的时候&#xff0c;我…