代码随想录算法训练营第16天|104. 二叉树的最大深度111.二叉树的最小深度222.完全二叉树的节点个数

JAVA代码编写

104. 二叉树的最大深度

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

输入:root = [1,null,2]
输出:2

提示:

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

教程:https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

视频:https://www.bilibili.com/video/BV1Gd4y1V75u/

方法一:递归

思路

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)

  • 空间复杂度: O ( n ) O(n) O(n)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    public static void main(String[] args) {
        // 创建一棵二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20, new TreeNode(15), new TreeNode(7));

        // 调用 maxDepth 方法计算二叉树的最大深度
        Solution solution = new Solution();
        int depth = solution.maxDepth(root);
        System.out.println("The maximum depth of the binary tree is: " + depth);
    }
}

在这里插入图片描述

111. 二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明:**叶子节点是指没有子节点的节点。

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:2

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

提示:

  • 树中节点数的范围在 [0, 105]
  • -1000 <= Node.val <= 1000

教程:https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

视频:https://www.bilibili.com/video/BV1QD4y1B7e2/

方法一:递归

思路

复杂度分析

  • 时间复杂度: O(n),其中 n 是树中节点的个数。

  • 空间复杂度: O(h),其中 h 是树的高度。

class Solution {
    public int minDepth(TreeNode root) {
        if(root ==null) return 0;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if(root.left == null){
            return rightDepth+1;
        }
        if(root.right == null){
            return leftDepth+1;
        }
        //左右结点都不为null
        return Math.min(leftDepth,rightDepth)+1;

    }
}

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

示例 1:

img

输入:root = [1,2,3,4,5,6]
输出:6

示例 2:

输入:root = []
输出:0

示例 3:

输入:root = [1]
输出:1

提示:

  • 树中节点的数目范围是[0, 5 * 104]
  • 0 <= Node.val <= 5 * 104
  • 题目数据保证输入的树是 完全二叉树

**进阶:**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗?

教程:https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html

视频:https://www.bilibili.com/video/BV1eW4y1B7pD/

方法一:递归

思路

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null)  return 0;
        int leftNodes= countNodes(root.left);
        int rightNodes = countNodes(root.right);
        return leftNodes+rightNodes+1;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/124891.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2023年下半年信息系统项目管理师下午真题及答案解析(第三批)

试题一(6分) 项目有A、B、C、D、E、F 6个活动&#xff0c;各活动的关系如下表&#xff1a; 2023年下半年信息系统项目管理师下午真题答案及解析 试题一(6分)

xshell和linux什么关系,其实很简单

如果你是从事网络安全相关的工作人员&#xff0c;那你一定对很多人xshell和linux这两词很熟悉&#xff0c;那么xshell和linux究竟是什么关系呢&#xff1f;今天就让小编给你详细讲讲。 xshell和linux什么关系 一、xshell和linux什么关系 Xsehll是一款在Windows平台上运行的远…

Python3简易接口自动化测试框架设计与实现

1、开发环境 操作系统&#xff1a;Ubuntu18开发工具&#xff1a;IDEAPyCharm插件Python版本&#xff1a;3.6 2、用到的模块 requests&#xff1a;用于发送请求xlrd&#xff1a;操作Excel&#xff0c;组织测试用例smtplib&#xff0c;email&#xff1a;发送测试报告logging&a…

Hadoop常见问题

报错1 &#xff1a;is group-writable, and the group is not root. Its permissions are 0775, datanode启动时&#xff0c;日志报错 1.“xxxx” is group-writable, and the group is not root. Its permissions are 0775, and it is owned by gid 3245. Please fix this…

Apipost-Helper:IDEA中的类postman工具

今天给大家推荐一款IDEA插件&#xff1a;Apipost-Helper-2.0&#xff0c;写完代码IDEA内一键生成API文档&#xff0c;无需安装、打开任何其他软件&#xff1b;写完代码IDEA内一键调试&#xff0c;无需安装、打开任何其他软件&#xff1b;生成API目录树&#xff0c;双击即可快速…

工业摄像机参数计算

在工业相机选型的时候有点懵&#xff0c;有一些参数都不知道咋计算的。有些概念也没有区分清楚。‘’ 靶面尺寸 CMOS 或者是 CCD 使用几分之几英寸来标注的时候&#xff0c;这个几分之几英寸计算的是什么尺寸&#xff1f; 一开始我以为这个计算的就是靶面的实际对角线的尺寸…

小程序发成绩

在这个数字化快速发展的时代&#xff0c;让学生能够方便快捷地获取自己的成绩已经成为一项基本的需求。那么&#xff0c;如何实现这一目标呢&#xff1f;对于许多老师来说&#xff0c;可能首先想到的是使用各种代码或者Excel来发布成绩查询。今天&#xff0c;我们就来探讨一下这…

《微服务架构设计模式》之三:微服务架构中的进程通信

概述 交互方式 客户端和服务端交互方式可以从两个维度来分&#xff1a; 维度1&#xff1a;一对一和多对多 一对一&#xff1a;每个客户端请求由一个实例来处理。 一对多&#xff1a;每个客户端请求由多个实例来处理。维度2&#xff1a;同步和异步 同步模式&#xff1a;客户端…

maven 上传本地jar包到nexus

maven上传命令 mvn deploy:deploy-file -DgroupIdcom.microsoft.sqlserver -DartifactIdsqljdbc4 -Dversion4.0 -Dpackagingjar -DfileC:\java\top-sdk-java-1.0.1-lib\lib\bcprov-jdk16-1.46.jar -Durlhttp://ip:port/repository/maven-releases/ -DrepositoryIdsnapshot…

Linux系统编程——文件的打开及创建

打开(open) 使用open函数需要包含以下三个头文件&#xff1a; #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> open的函数定义格式 int open(const char *pathname,int flags); int open(const char *pathname,int flags,mode_t mode…

C语言 变量

C 变量 变量其实只不过是程序可操作的存储区的名称。C 中每个变量都有特定的类型&#xff0c;类型决定了变量存储的大小和布局&#xff0c;该范围内的值都可以存储在内存中&#xff0c;运算符可应用于变量上。 变量的名称可以由字母、数字和下划线字符组成。它必须以字母或下…

POI.5.2.4常用操作-数据导入导出常规操作

1、APACHE POI简介 Apache POI 简介是用Java编写的免费开源的跨平台的 Java API&#xff0c;Apache POI提供API给Java程式对Microsoft Office&#xff08;Excel、WORD、PowerPoint、Visio等&#xff09;格式档案读和写的功能。 1.1、其他操作Excel工具 Java Excel是一开放源码…

pda超高频RFID工业手持终端,远距离多标签读取神器

RFID技术的基本原理是通过射频信号进行通信。RFID系统由两部分组成&#xff0c;一是RFID读写器&#xff0c;二是RFID标签。读写器通过发送射频信号&#xff0c;激活标签&#xff0c;并从标签中读取存储的数据。标签可以附着在物品上&#xff0c;并携带物品的相关信息。当物品通…

Codeforces Round 908 (Div. 2)题解

目录 A. Secret Sport 题目分析: B. Two Out of Three 题目分析: C. Anonymous Informant 题目分析: A. Secret Sport 题目分析: A,B一共打n场比赛&#xff0c;输入一个字符串由A和‘B’组成代表A赢或者B赢&#xff08;无平局&#xff09;&#xff0c;因为题目说明这个人…

迅为龙芯3A5000主板,支持PCIE 3.0、USB 3.0和 SATA 3.0显示接口2 路、HDMI 和1路 VGA,可直连显示器

性能强 采用全国产龙芯3A5000处理器&#xff0c;基于龙芯自主指令系统 (LoongArch)的LA464微结构&#xff0c;并进一步提升频率&#xff0c;降低功耗&#xff0c;优化性能。 桥片 桥片采用龙芯 7A2000&#xff0c;支持PCIE 3.0、USB 3.0和 SATA 3.0显示接口2 路、HDMI 和1路 …

9 网关的作用

1、总结&#xff1a; 1.如果离开本局域网&#xff0c;就需要经过网关&#xff0c;网关是路由器的一个网口。 2.路由器是一个三层设备&#xff0c;里面有如何寻找下一跳的规则 3.经过路由器之后 MAC 头要变&#xff0c;如果 IP 不变&#xff0c;相当于不换护照的欧洲旅游&#…

HBase学习笔记(1)—— 知识点总结

目录 HBase概述 HBase 基本架构 HBase安装部署启动 HBase Shell HBase数据读写流程 HBase 优化 HBase概述 HBase是以 hdfs 为数据存储的&#xff0c;一种分布式、非关系型的、可扩展的 NoSQL 数据库 关系型数据库和非关系型数据库的区别&#xff1a; 关系型数据库和非关…

UT代码编译至build文件夹

得克萨斯大学奥斯汀分校代码&#xff1a;代码文件按照网上很多的做法是直接**cmake .****make**则会出现以下的内容&#xff1a;但是这样做未免有些杂乱&#xff0c;会将编译生成的Makefile和其他数据文件全部存放在utaustinvilla3d-master下&#xff0c;比较杂乱。根据我们编译…

Linux--gcc与make

文章目录 gcc/g的使用背景知识gcc与ggcc的编译过程预处理编译汇编链接 函数库自动化构建工具--make三个时间伪目标文件其他表示方法mybin的推导过程 gcc/g的使用 背景知识 GCC是一个开源的编译器套件&#xff0c;支持多种编程语言&#xff0c;并提供了广泛的语言特性和标准库…

C++入门学习(4)引用 (讲解拿指针比较)

上期回顾 在学习完函数重载之后&#xff0c;我们可以使用多个重名函数进行操作&#xff0c;会发现C真的是弥补了好多C语言的不足之处&#xff0c;真的不禁感概一下&#xff0c;时代的进步是需要人去做出改变的&#xff0c;而不是一味的使用啊&#xff01;所以我们今天继续学一下…