算法日记day 17（二叉树的最大、最小深度）

一、二叉树的最大深度

题目：

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

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

示例 1：

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

示例 2：

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

思路：

采用后序遍历的方法，一层一层的去判断子节点与父节点的距离，可以将一整个二叉树转变为一个个独立开来的二叉树，然后分别判断距离，在逐渐返回上一层，直到返回到根节点为止

代码：

public int maxDepth(TreeNode root) {// 如果根节点为空，即空树，深度为 0if (root == null) return 0;// 递归计算左子树的最大深度int leftDepth = maxDepth(root.left);// 递归计算右子树的最大深度int rightDepth = maxDepth(root.right);// 当前节点的深度为左右子树最大深度的较大值加上当前节点的深度 1int depth = Math.max(leftDepth, rightDepth) + 1;// 返回当前节点的深度return depth;
}
  • 首先进行判断，如果 root 为 null，即空树，则深度为 0。
  • 否则，分别递归计算左子树 root.left 和右子树 root.right 的最大深度。
  • 使用 Math.max 方法比较左右子树的最大深度，然后加上当前节点的深度 1，得到当前节点为根的子树的最大深度 depth。
  • 最后返回计算得到的 depth 值作为结果。
  • maxDepth 方法通过递归调用自身，深度优先地计算每个节点的深度。
  • 如果树为空，则最大深度为 0。
  • 否则，通过递归分别计算左右子树的深度，并根据子树深度的比较确定当前子树的最大深度。
  • 返回的最终深度值代表整棵树的最大深度。

 此外代码还可以进行简化

public int maxDepth(TreeNode root) {if (root == null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

二、二叉树的最小深度

题目：

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

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

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

示例 1：

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

示例 2：

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

思路：

代码与最大深度类似，但是有个误区，如果出现了左子树或者右子树一边为null的情况，最终结果就为1了，但是实际上这并不是从根节点到最近叶子节点的最短路径上的节点数量，因此需要额外的做出判断

代码：

public int minDepth(TreeNode root) {if (root == null) {return 0;}// 递归计算左子树的最小深度int leftDepth = minDepth(root.left);// 递归计算右子树的最小深度int rightDepth = minDepth(root.right);// 如果当前节点的左子树为空，右子树不为空，则最小深度为右子树的深度 + 1if (root.left == null && root.right != null) {return 1 + rightDepth;}// 如果当前节点的右子树为空，左子树不为空，则最小深度为左子树的深度 + 1if (root.left != null && root.right == null) {return 1 + leftDepth;}// 否则，当前节点的最小深度为左右子树最小深度的较小值 + 1return 1 + Math.min(leftDepth, rightDepth);
}

  1. 空树情况：

    • 如果 root 为 null，即空树，则最小深度为 0，因此直接返回 0。

  2. 非空树情况：

    • 首先递归计算左子树的最小深度 leftDepth。
    • 然后递归计算右子树的最小深度 rightDepth。

  3. 叶子节点情况：

    • 如果当前节点 root 的左子树为空但右子树不为空，则最小深度为右子树的深度 + 1。这是因为要考虑到最小深度是从根节点到叶子节点的路径，所以只有右子树的情况需要特别处理。
    • 同理，如果当前节点的右子树为空但左子树不为空，则最小深度为左子树的深度 + 1。

  4. 一般情况：

    • 如果当前节点既有左子树又有右子树，则最小深度为左右子树最小深度的较小值 + 1

 

三、完全二叉树节点的数量 

题目：

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

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

示例 1：

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

示例 2：

输入：root = []
输出：0

示例 3：

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

方法有很多

1、层序遍历

public int countNodes(TreeNode root) {if (root == null) {return 0;}// 递归计算左子树中节点的总数int leftNum = countNodes(root.left);// 递归计算右子树中节点的总数int rightNum = countNodes(root.right);// 当前节点(root)本身加上左右子树的节点数之和return 1 + leftNum + rightNum;
}

时间复杂度为O(n) 

2、利用完全二叉树的性质

思路：

由于完全二叉树不存在只有右子树而没有左子树的情况，因此我们可以通过判断左右子树最左边的节点和最右边节点的深度差来判断该二叉树中节点的数量，这样很大一部分中间的节点就没必要再次遍历，时间复杂度自然就小于O(n)了

代码：

public int countNodes(TreeNode root) {if (root == null) {return 0;}// 定义变量保存左子树和右子树TreeNode left = root.left;TreeNode right = root.right;int leftCount = 0, rightCount = 0;// 计算左子树的高度（即左子树的叶子节点数）while (left != null) {left = left.left;leftCount++;}// 计算右子树的高度（即右子树的叶子节点数）while (right != null) {right = right.right;rightCount++;}// 如果左子树的叶子节点数等于右子树的叶子节点数，则说明是满二叉树if (leftCount == rightCount) {// 计算满二叉树的节点总数并返回return (2 << leftCount) - 1;}// 如果不是满二叉树，则递归计算左右子树的节点总数，并加上当前节点int leftNum = countNodes(root.left);int rightNum = countNodes(root.right);return 1 + leftNum + rightNum;
}

  1. 空树情况：

    • 如果 root 为 null，即空树，则节点总数为 0，直接返回 0。

  2. 非空树情况：

    • 首先定义 left 和 right 变量分别指向根节点的左子树和右子树。
    • 使用 leftCount 和 rightCount 分别记录左子树和右子树的叶子节点数（即高度）。
    • 这里通过 while 循环找到左子树和右子树的最深的叶子节点，从而得到左右子树的高度。

  3. 判断满二叉树：

    • 如果左子树的叶子节点数 leftCount 等于右子树的叶子节点数 rightCount，则说明当前子树是满二叉树。
    • 满二叉树的节点总数可以通过公式 (2 << leftCount) - 1 计算得到，即 2^leftCount - 1。

  4. 非满二叉树情况：

    • 如果左右子树的叶子节点数不相等，则该二叉树不是满二叉树。
    • 需要递归计算左右子树的节点总数，并将当前节点加上去（即加 1）。

  5. 递归调用：

    • 如果不是满二叉树，则递归计算左子树和右子树的节点总数，分别存储在 leftNum 和 rightNum 中。
    • 最终返回的节点总数是当前节点 root 本身加上左右子树的节点总数。

3、迭代法 （BFS）

思路：

利用队列存储完全二叉树的所有节点，最后节点总数

代码：

public int countNodes(TreeNode root) {if (root == null) return 0; // 如果根节点为空，直接返回节点总数为0Queue<TreeNode> queue = new LinkedList<>(); // 创建一个队列用于BFSqueue.offer(root); // 将根节点加入队列int result = 0; // 初始化节点总数为0while (!queue.isEmpty()) { // 当队列不为空时循环int size = queue.size(); // 获取当前队列的大小，即当前层的节点数while (size-- > 0) { // 遍历当前层的所有节点TreeNode cur = queue.poll(); // 出队一个节点result++; // 节点总数加1，表示访问了一个节点// 将当前节点的左右子节点加入队列（如果存在）if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}}return result; // 返回节点总数
}

  1. 初始条件检查：

    • 首先检查根节点 root 是否为空。若为空，则整棵树没有节点，直接返回节点总数为0。

  2. 队列初始化：

    • 创建一个 Queue<TreeNode> 类型的队列 queue，使用 LinkedList 实现。

  3. BFS遍历：

    • 将根节点 root 加入队列 queue。
    • 初始化节点总数 result 为0，用于统计访问过的节点数。

  4. 主循环：

    • 使用 while (!queue.isEmpty()) 进行 BFS 的迭代，直到队列为空。
    • 在每次迭代中，获取当前队列的大小 size，表示当前层的节点数。

  5. 处理当前层节点：

    • 通过 size-- > 0 的循环方式遍历当前层的所有节点：
      • 从队列中取出一个节点 cur。
      • 将 result 增加1，表示访问了一个节点。

  6. 扩展下一层：

    • 检查当前节点 cur 的左右子节点是否存在，如果存在则加入队列 queue 中，以便在下一次迭代时处理。

 

四、平衡二叉树 

题目：

给定一个二叉树，判断它是否是 

平衡二叉树

示例 1：

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

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

思路：

是否平衡的前提是要判断左右子树的高度差是否平衡，采用后序遍历的方法，从叶子节点逐层向上排查左右子树高度差，若高度差大于1则不是平衡二叉树

代码：

递归计算每个节点的高度，并判断是否平衡

public int getHeight(TreeNode root) {if (root == null) {return 0; // 空节点的高度为0}int leftHeight = getHeight(root.left); // 获取左子树的高度int rightHeight = getHeight(root.right); // 获取右子树的高度// 如果左子树或右子树不是平衡的，则整棵树也不平衡，返回-1if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {return -1;}// 返回当前节点为根的子树的高度return Math.max(leftHeight, rightHeight) + 1;
}
  • 如果 root 为 null，则返回高度 0。
  • 分别计算左子树和右子树的高度 leftHeight 和 rightHeight。
  • 如果左子树或右子树的高度为 -1，或者左右子树的高度差大于 1，则返回 -1，表示当前子树不是平衡的。
  • 否则，返回当前节点为根的子树的高度，即 Math.max(leftHeight, rightHeight) + 1。
//调用 getHeight(root) 方法，如果返回的高度不等于 -1，则说明是平衡二叉树；否则，不是平衡二叉树。
public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;
}

这种方法的时间复杂度为 O(n)，其中 n 是二叉树的节点数，因为每个节点都需要计算其高度一次。

今天的学习就到这里 

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

Redis底层数据结构-双向链表

Redis底层数据结构-双向链表

链表提供了高效的节点重排能力&#xff0c;以及顺序性的节点访问方式&#xff0c;并且可以通过增删节点来灵活地调整链表的长度。C语言并没有内置这种数据结构&#xff0c;独立实现。 实现 节点结构adlist.h/listNode typedef struct listNode {// 前置节点struct listNode …
阅读更多...
pycharm的开头中设置作者开发时间等信息成为模板

pycharm的开头中设置作者开发时间等信息成为模板

就是在pycharm中写代码的时候&#xff0c;开头会有一些代码相关的信息&#xff0c;比如说作者&#xff0c;比如说开发时间等等&#xff0c;如果每次都写比较麻烦&#xff0c;其实pycharm中可以设置成模板&#xff0c;而且时间还会自动更新。 一&#xff0c;打开pycharm点文件&…
阅读更多...
Django cursor()增删改查和shell环境执行脚本

Django cursor()增删改查和shell环境执行脚本

在Django中&#xff0c;cursor()方法是DatabaseWrapper对象&#xff08;由django.db.connectio提供&#xff09;的一个方法&#xff0c;用于创建一个游标对象。这个游标对象可以用来执行SQL命令&#xff0c;从而实现对数据库的增删改查操作。 查询&#xff08;Select&#xff0…
阅读更多...
设计分享—国外医疗行业界面设计

设计分享—国外医疗行业界面设计

医疗诊断界面是一个直观且信息丰富的数字平台&#xff0c;它集成了患者基本信息、病史记录、当前症状描述、检查结果展示以及智能诊断建议等功能于一体。 界面设计简洁明了&#xff0c;便于医生快速浏览关键信息&#xff0c;同时利用先进的算法辅助医生进行精准诊断&#xff0…
阅读更多...
鸿蒙系统（java方法以及数据结构）

鸿蒙系统（java方法以及数据结构）

在java中数据结构是以类和对象的形式实现的&#xff0c;常见的数据结构及其简单实现 1.数组&#xff08;Array&#xff09; 2.链表&#xff08;Linked List&#xff09; 3.栈&#xff08;Stack&#xff09; 4.队列&#xff08;Queue&#xff09; 5.哈希表&#xff08;Hash…
阅读更多...
elasticsearch8.14.1集群安装部署

elasticsearch8.14.1集群安装部署

elasticsearch安装部署&#xff0c;首先需要准备至少三台服务器&#xff0c;本例再windows11下安装三台vmware虚拟机&#xff0c;利用centOS7系统模拟服务器环境。 本例假设你已经安装了三台vmware和centOS7&#xff0c;且centOS7运行正常。接下来我们直接讲解elasticsearch下载…
阅读更多...
Linux（linux命令）和Window（powershell）的查找命令

Linux（linux命令）和Window（powershell）的查找命令

目录 LinuxWindow基本操作（1）Get-ChildItem（2）Get-ChildItem模糊查找1. 使用星号（*）通配符（常用）1、第一个命令：使用 `-Filter` 参数（常用）2、第二个命令：使用管道和 `Where-Object`3、差异2. 使用问号（?）通配符（不常用）3. 结合使用星号和问号（不常用）4. 使…
阅读更多...
3GPP R18 Multi-USIM是怎么回事？(四)

3GPP R18 Multi-USIM是怎么回事？(四)

前几篇主要是MUSIM feature NAS 部分内容的总结，这篇开始看RRC部分相关的内容，由于RRC部分内容过长，也分成了2篇。这篇就着重看下musim gap以及RRC触发UE离开RRC Connected mode相关的内容，直入正题， 上面的内容在overview中有提到，对应的是如下38.300中的描述。 处于网络…
阅读更多...
【python 已解决】ZeroDivisionError: division by zero —— 深度解析与解决策略

【python 已解决】ZeroDivisionError: division by zero —— 深度解析与解决策略

【python 已解决】ZeroDivisionError: division by zero —— 深度解析与解决策略 在编程过程中&#xff0c;尤其是使用Python这类高级编程语言时&#xff0c;ZeroDivisionError是一个常见的运行时错误。这个错误发生时&#xff0c;意味着你的代码中尝试进行了除以零的操作&am…
阅读更多...
【深度学习】yolov8-seg分割训练，拼接图的分割复原

【深度学习】yolov8-seg分割训练，拼接图的分割复原

文章目录 项目背景造数据训练 项目背景 在日常开发中&#xff0c;经常会遇到一些图片是由多个图片拼接来的&#xff0c;如下图就是三个图片横向拼接来的。是否可以利用yolov8-seg模型来识别出这张图片的三张子图区域呢&#xff0c;这是文本要做的事情。 造数据 假设拼接方式有…
阅读更多...
wireshark过滤器，如何使用wireshark捕获指定域名的流量

wireshark过滤器，如何使用wireshark捕获指定域名的流量

过滤器比较高级&#xff0c;但是也很重要&#xff0c;我决定通过一个案例来学习过滤器的知识点。 比如&#xff0c;我现在访问 zhangdapeng.com 我希望能够捕获关于这个域名下的流量&#xff0c;该如何实现呢&#xff1f; 我选择了捕获以太网的流量&#xff0c;但是目前捕获到…
阅读更多...
【Linux】从零开始认识多线程 --- 线程ID

【Linux】从零开始认识多线程 --- 线程ID

在这个浮躁的时代 只有自律的人才能脱颖而出 -- 《觉醒年代》 1 前言 上一篇文章中讲解了线程控制的基本接口&#xff1a; 线程创建pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);: pthread_t *thread :输出…
阅读更多...
43 华三AC登录Web页面

43 华三AC登录Web页面

一 无线上WEB页面 1 创建vlan 56 [AC-KongZhi]vlan 56 2 退出 [AC-KongZhi-vlan56]quit 3 进入vlan三层口 配置IP地址 [AC-KongZhi]interface Vlan-interface 56 [AC-KongZhi-Vlan-interface56]ip address 192.168.56.55 24 4 在AC控制器与Host主机的接口上能通关vlan 5…
阅读更多...
MySQL进阶之（十）事务和隔离级别

MySQL进阶之（十）事务和隔离级别

十、事务和隔离级别 10.1 事务10.1.1 事务介绍10.1.2 事务四大特性10.1.3 事务的状态10.1.4 如何使用事务01、事务控制语句02、事务操作 10.2 事务的隔离级别10.2.1 事务数据可见性和并发问题01、脏写&#xff08;Dirty Write&#xff09;/更新丢失02、脏读&#xff08;Dirty R…
阅读更多...
Python怎样读取URL生成PDF

Python怎样读取URL生成PDF

1. 安装依赖的exe 需要在这个网址&#xff0c;安装一个exe包&#xff0c;地址&#xff1a;https://wkhtmltopdf.org/ 进入网址后&#xff0c;点这个位置&#xff1a; 选择一个你的操作系统的下载链接&#xff1a; 安装后的exe文件&#xff1a; C:\Program Files\wkhtmltopdf…
阅读更多...
分布式服务框架zookeeper+消息队列kafka

分布式服务框架zookeeper+消息队列kafka

一、zookeeper概述 zookeeper是一个分布式服务框架&#xff0c;它主要是用来解决分布式应用中经常遇到的一些数据管理问题&#xff0c;如&#xff1a;命名服务&#xff0c;状态同步&#xff0c;配置中心&#xff0c;集群管理等。 在分布式环境下&#xff0c;经常需要对应用/服…
阅读更多...
【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第四十四章 注册字符设备号

【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第四十四章 注册字符设备号

i.MX8MM处理器采用了先进的14LPCFinFET工艺&#xff0c;提供更快的速度和更高的电源效率;四核Cortex-A53&#xff0c;单核Cortex-M4&#xff0c;多达五个内核 &#xff0c;主频高达1.8GHz&#xff0c;2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…
阅读更多...
硅谷裸机云大宽带服务器连接不上是怎么回事？该如何处理

硅谷裸机云大宽带服务器连接不上是怎么回事？该如何处理

硅谷裸机云大宽带服务器连接不上的常见原因主要有网络设置、网络设备、服务端、软件和服务、物理层等&#xff0c;出现以上问题&#xff0c;RAK部落小编建议大家可以通过以下一系列的方法进行排查和解决。具体分析如下&#xff1a; 1.检查网络设置 　　核对配置信息&#xff1a…
阅读更多...
微信小程序-CANVAS写入图片素材、文字等数据生成图片

微信小程序-CANVAS写入图片素材、文字等数据生成图片

微信小程序中&#xff0c;CANVAS写入图片素材、文字等数据生成图片&#xff0c;最终可将生成的 base64 格式图片保存至相册操作 Tips&#xff1a; 1、canvas 标签默认宽度 300px、高度 150px canvas 生成图片时&#xff0c;写入图片素材、文字等数据前&#xff0c;需要根据实…
阅读更多...
LangChain的使用详解

LangChain的使用详解

一、 概念介绍 1.1 Langchain 是什么&#xff1f; 官方定义是&#xff1a;LangChain是一个强大的框架&#xff0c;旨在帮助开发人员使用语言模型构建端到端的应用程序&#xff0c;它提供了一套工具、组件和接口&#xff0c;可简化创建由大型语言模型 (LLM) 和聊天模型提供…
阅读更多...
最新文章

Copyright @ 2022~2023