算法-二叉树-简单-二叉树的直径、将有序数组转换成二叉搜索树

记录一下算法题的学习9

二叉树的直径

题目:给你一棵二叉树的根节点,返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示

读完题目,我们很容易联系到我们做过的二叉树的最大深度

算法-二叉树-简单-二叉树的最大和最小深度-CSDN博客

举例视图,便于观察

 由图可知:我们现在先求左子树的最大深度(加上根节点),即[6,4,3,2]----->4,而右子树的最大深度(加上根节点)为[6,9,10]or[6,9,8]---->3,但是这是最大深度是最多节点数,直径是树中任意两个节点之间最长路径的长度,即2和10 或者 2和8之间的连线边数,所以是右子树的最大深度+左子树的最大深度-2得到最长路径

 

这张图就是左子树深度[6,4,3,2]-->4,右子树深度[6]-->1(这是算上了根节点),右子树的最大深度+左子树的最大深度-2得到最长路径 即3

 深度优先搜索代码展示:

//这道题很容易联想到二叉树的最大深度这道题目,我们现在就需要求二叉树的最大深度,在去求直径
class Solution {
     int ans=0;
      public int maxDepth(TreeNode node) {
        //访问到空节点,返回0
       if(node==null){
           return 0;
       }
       int leftDepth=maxDepth(node.left)+1; //得到根节点root左子树的最长路径上的节点数
       int rightDepth=maxDepth(node.right)+1;//得到根节点root右子树的最长路径上的节点数
       ans=Math.max(ans,leftDepth+rightDepth-2);//这里的思考关键: 二叉树的直径就是左子树的最多节点数+右子树上的最多节点数-2
      return Math.max(leftDepth,rightDepth);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return ans;//最长路径
}

     
}

将有序数组转换成二叉搜索树

题目:

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。  

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

 题目分析:根据数组 元素升序排列,我们可以想到二叉树的中序遍历顺序是左根右

举例nums[-10,-3,0,5,9]

nums-10-3059
index01234

选择中间位置左边的数字作为根节点(0+4)/2=2 j即0作为根节点root

0的左孩子是root.left=balance(nums,0,1)即-3,

balance(nums,0,0)即-10,balance(nums,0,-1)即null

0的右孩子是root.right=balance(nums,3,4)即5,

balance(nums,4,4)即9,balance(nums,5,4)即null

题目答案这张图也是符合正确的(但是我没想明白,感谢指正)

 

代码展示: 

class Solution {
    public TreeNode balance(int[] nums, int left, int right) {
        //如果左边值大于右边值返回null
        if (left > right) {
            return null;
        }
        //如果数组元素是奇数,根节点的选择是唯一的
        //如果数组元素是偶数,选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;
        //如果数组元素是偶数 选择中间位置右边的数字作为根节点
        // int mid = (left + right + 1) / 2;
        TreeNode root = new TreeNode(nums[mid]);//根节点出现

        root.left = balance(nums, left, mid - 1);//获取根节点左孩子
        root.right = balance(nums, mid + 1, right);//获取根节点右孩子
        return root;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        //这里先初始数组,获取数组元素的第一个索引和最后一个元素的索引
        return balance(nums,0,nums.length-1);
    }
}

结束拜拜!

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

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

相关文章

如何打造适用的MES管理系统解决方案

在当前的制造业领域,项目型生产企业面临着独特的挑战。尽管国外的大型软件公司提供了某些解决方案,但由于地域、文化和制度的差异,这些方案并不完全满足企业的实际需求。为了解决这一难题,我们必须以客户为中心,围绕他…

机器学习中的特征选择:方法和 Python 示例

布拉加德什桑达拉拉詹 一、说明 特征选择是机器学习流程中至关重要且经常被低估的步骤。它涉及从数据集中的原始特征集中选择最相关的特征(输入变量或属性)的子集。特征选择的重要性怎么强调都不为过,因为它直接影响机器学习模型的质量、效率…

【C++】类与对象(中)

一、类的默认成员函数 如果一个类中什么成员都没有,简称为空类。 空类中真的什么都没有吗?并不是,任何类在什么都不写时,编译器会自动生成以下6个默认成员函数。 默认成员函数:用户没有显式实现,编译器会自…

解析大型语言模型的训练、微调和推理的运行时性能

背景 这篇论文是截至目前为数不多的介绍大模型训练配套环境比对的论文,对于想要入门大模型训练同学是个不错的入门资料。比较了不同尺寸模型(比较常用的7、13、70b),在不同型号gpu、训练框架、推理框架数据。结合自己实际工作需要…

华为认证 | HCIE考证流程详解!

HCIE(Huawei Certified ICT Expert,华为认证ICT专家)是华为认证体系中最高级别的ICT技术认证,旨在打造高含金量的专家级认证,为技术融合背景下的ICT产业提供新的能力标准,以实现华为认证引领ICT行业技术认证…

numpy报错:AttributeError: module ‘numpy‘ has no attribute ‘float‘

报错:AttributeError: module numpy has no attribute float numpy官网:NumPy 报错原因:从numpy1.24起删除了numpy.bool、numpy.int、numpy.float、numpy.complex、numpy.object、numpy.str、numpy.long、numpy.unicode类型的支持。 解决办法…

小程序Tab栏与页面滚动联动

小程序tab栏切换与页面滚动联动 tab栏与页面滚动联动点击tab栏页面跳到指定位置滚动页面时切换tab栏 tab栏与页面滚动联动 在进行小程序开发时,需要实现点击tab栏页面滚动到某一指定位置,并且滚动页面时,小程序的tab栏进行切换。 在一开始&a…

MP3音频文件体积怎么缩小?压缩的方法有哪些?

压缩音频文件可减小文件的大小,从而更轻松地上传到其他平台,或轻松的通过电子邮件进行分享。除此之外,压缩音频文件还可以节省硬盘上的储存空间。那MP3音频文件体积怎么缩小呢?继续阅读可查看压缩的详细流程。 什么是音频文件压缩…

开发上门按摩系统对技师如何管理,薪资结构怎么设计

开发完上门按摩系统平台上线之后,对技师的管理和薪资结构是非常重要的环节,关乎着平台的服务能力和服务质量,那么应该如何去管理和设计薪资结构呢 首先说技师管理: 一、培训和认证:平台应对技师进行全面的培训&#xf…

ArkTS声明式开发范式

装饰器 用来装饰类、结构体、方法以及变量,赋予其特殊的含义,如上述示例中 Entry 、 Component 、 State 都是装饰器。 Component 表示这是个自定义组件; Entry 则表示这是个入口组件; State 表示组件中的状态变量,…

CRM商机管理软件:构建客户为中心的管理理念

企业为什么选择CRM商机管理软件?1.CRM软件能够帮助企业建立以客户为中心的管理理念;2.CRM商机管理软件全面直观的展示客户数据;3.市场人员可以制订个性化的营销策略;4.移动应用为外出的销售带来的便利。 1.构建客户为中心的管理理…

AI 智能时代,如何快速搞懂向量数据库库?

▼最近直播超级多,预约保你有收获 今晚20点直播:《大模型向量数据库技术架构剖析以及应用实战》 —1— 向量数据库为什么如此重要? AI 智能时代,向量数据库是人人需要掌握的必备技能,为什么这么说? 对标移…

Qt程序的自定义安装卸载方案

前言 NSIS 是一个 Open Source 的 Windows 系统下安装程序制作程序; NSIS-UI-Plugin 是一个开源的NSIS UI插件; 0x0 环境搭建 https://www.cnblogs.com/NSIS/p/16581122.html https://github.com/sway913/NSIS-UI-Plugin 0x1 类图 0x2 二次开发 自定…

关键性进展! 小米造车露真容 预计明年上市

大家好,我是极智视界,欢迎关注我的公众号,获取我的更多前沿科技分享 邀您加入我的知识星球「极智视界」,星球内有超多好玩的项目实战源码和资源下载,链接:https://t.zsxq.com/0aiNxERDq 小米在各种不同的产品上都在不断打上自己的品牌,这绝对不止于智能手机,而是有智能…

梨花声音课堂,真诚和情感展现家庭生活场景,易使观众产生共鸣

在为家庭剧的配音工作时,配音员要能够传递出剧中角色在日常生活中所经历的情感波动,以及家庭关系中的温情、矛盾和解决问题的过程。家庭剧着重描绘亲情纽带和人物间的真挚交往,因此配音的真实感和情感表达尤为重要。以下是针对家庭剧配音的几…

毕业设计2049网上选课系统JSP【程序源码+文档+调试运行】

摘要 本文详细介绍了一个网上选课系统的设计与实现过程。该系统主要分为学生用户、管理员和教师用户三个模块,涵盖了用户登录、在线选课、信息管理、密码修改等功能。通过对系统功能的分析,进行了数据库设计和界面设计,并进行了测试和优化。…

系列五、为什么不用线程id作为ThreadLocalMap的key

一、为什么不用线程id作为ThreadLocalMap的key 1.1、案例代码 /*** Author : 一叶浮萍归大海* Date: 2023/11/21 11:50* Description: 需求:* 如果当前线程是线程1,那么设置书名和作者分别为 三国演义 罗贯中* 如果…

Linux主机间的相互免秘钥

主机间的相互免秘钥 1.生成密钥 ssh-keygen -t rsa -P -f ~/.ssh/id_rsa运行以上命令后会在 ~/.ssh/ 目录下生成一对密钥对。 2.拷贝公钥 把自己的公钥传递给对方主机即可,这个公钥文件必须放在对方主机的~/.ssh/authorized_keys 文件中。 ssh-copy-id -i ~/.s…

如何选择一款快速可靠的文件自动同步软件?

在企业的数据流转管控过程中,经常会遇到频繁的数据备份、同步,人工重复这样的工作程序,既繁琐又容易出错。越来越多的企业,要求内部各种业务数据在多台服务器之间、多个数据中心之间,乃至多云和本地之间调度和同步。很…

JVM 之 class文件详解

目录 一. 前言 二. class文件结构 2.1. 文件格式 2.2. 魔数与版本号 2.3. 常量池 2.4. 访问标志 2.5. 类索引、父类索引和接口索引集合 2.6. 字段表集合 2.7. 方法表集合 2.8. 属性表集合 2.8.1. Code 属性表 2.8.2. Exceptions 属性 2.8.3. LineNumberTable 属性…