力扣hot100:543. 二叉树的直径/108. 将有序数组转换为二叉搜索树

一、543. 二叉树的直径

LeetCode:543. 二叉树的直径
在这里插入图片描述

二叉树的直径 = 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度

遇到二叉树的问题很容易去直接用求解的目标去定义递归函数。但是仔细考虑,返回树的直径并不能向上传播。因此我们可以拆分成两步:

  • 树的直径 = 左儿子的高度 + 右儿子的高度 + 2

因此我们只需要求高度就行。

树求高度实际上是一个树形dpdp[root] = max(dp[child]) +1

class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {max_len = 0;height(root);return max_len;}
private:int height(TreeNode * root){if(!root) return -1;//没有结点时,高度为-1。有一个结点时,高度为0int left_height = height(root->left);//左儿子高度int right_height = height(root->right);//右儿子高度max_len = max(max_len, left_height + right_height + 2);return max(left_height, right_height) + 1;//返回以root为根的子树的高度。}int max_len;
};

二、108. 将有序数组转换为二叉搜索树

LeetCode:108. 将有序数组转换为二叉搜索树
在这里插入图片描述
二叉搜索树(二叉查找树) : 对于任意节点,其左子树的所有节点的值小于该节点的值,其右子树的所有节点的值大于等于该节点的值。
这里需要注意的是,题目所给的nums 按 严格递增 顺序排列。因此,我们可以根据平衡二叉查找树的性质(左右子树高度差不大于1),通过下标直接找到根结点的位置(中间位置的结点)。

  • 当总结点个数为奇数时,中间位置的结点左右两边的结点个数相同,很显然左右子树结点个数相同,采用相同形状则高度是相同的。
  • 当总结点个数为偶数时,中间位置的结点右边的结点个数 比 左边结点个数多1。对于本中间位置结点而言,由于左右子树的生成规则相同,右子树的高度最多比左子树的高度多1。
  • 程序递归执行,因此所有结点皆满足这样的性质,则可以构建一颗平衡二叉树。

类似于:构建完全二叉查找树

class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return createTree(nums, 0, nums.size()-1);}
private:TreeNode * createTree(vector<int> & nums, int L, int R){if(L > R) return nullptr;int mid = (L + R) >> 1;TreeNode * root = new TreeNode(nums[mid], createTree(nums, L, mid - 1), createTree(nums, mid + 1, R));return root;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

SolidWorks进行热力学有限元分析二、模型装配

1.先打开软件&#xff0c;新建装配体 2.选中你要装配的零件&#xff0c;直接导入就行 3.鼠标点击左键直接先放进去 4.开始装配&#xff0c;点配合 5.选择你要接触的两个面&#xff0c;鼠标右键确定&#xff0c;然后把剩下的面对齐一下就行了 6.搞定

学习《现代密码学——基于安全多方计算协议的研究》 第一章

目录 前言 第1章 绪论 1.1 密码学的发展历史 1.2 现代密码学体制 1.3 现代密码学与安全多方计算 前言 近几年来&#xff0c;云计算、物联网、移动互联网等新概念、新技术被先后提出&#xff0c;促使信息技术飞速发展。同时&#xff0c;人类生活、沟通方式也随着新技术的普及…

泰克MDO3024示波器如何调整衰减倍数?

泰克MDO3024示波器是一款高性能的数字示波器&#xff0c;具备多种功能和调节选项&#xff0c;可以满足各种测试需求。其中一个重要的调节选项就是调整衰减倍数&#xff0c;通过调整衰减倍数&#xff0c;可以改变示波器的灵敏度和测量范围&#xff0c;帮助我们更好地观察和分析信…

奇诡 matlab 小 bug matlab git需要记录的改动太多

似乎是我有一次添加了太多的路径之后的事情。但是不敢说一定是这个导致的&#xff1a; 症状&#xff1a;只要对文本进行任何编辑操作&#xff0c;工作区就会出现"Processing … Cancel"的提示&#xff0c;如果不管的话这个提示不会消失&#xff0c;同时matlab变得越来…

【进程终止】退出信号 | 三种退出情况 | 如何进程终止returnexit_exit

目录 退出码 退出信号 进程终止情况3 如何进程终止 return退出 库函数exit 系统调用函数_exit ​exit和_exit的区别缓冲区 exit _exit 退出码 回顾上篇 代码跑完&#xff0c;结果正确&#xff08;退出码为0&#xff09;代码跑完&#xff0c;结果不正确&#xff08;退…

springboot项目组合定时器schedule注解实现定时任务

springboot项目组合定时器schedule注解实现定时任务&#xff01; 创建好springboot项目后&#xff0c;需要在启动类上增加注解开启定时器任务 下图所示&#xff1a; 增加这个注解&#xff0c;启动项目&#xff0c; package com.example.scheduledemo.util;import org.springf…

Linux进程通信-信号

信号概念 信号是 Linux 进程间通信的最古老的方式之一&#xff0c;是事件发生时对进程的通知机制&#xff0c;有时也称之为软件中断&#xff0c;它是在软件层次上对中断机制的一种模拟&#xff0c;是一种异步通信的方式。信号 可以导致一个正在运行的进程被另一个正在运行的异…

企业怎样进行IT外包以及IT外包服务内容

在数字化时代的浪潮中&#xff0c;企业逐渐认识到信息技术的关键作用&#xff0c;特别是制造业基地对于IT外包和运维服务的需求持续增长。然而&#xff0c;在诸多可供选择的IT外包和运维方案中&#xff0c;企业如何推动与IT外包公司的合作&#xff1f;本文将深入介绍IT外包方案…

nginx 启动,查看,停止

nginx 启动&#xff0c;查看&#xff0c;停止 启动 start nginx 查看是否启动成功 tasklist | findstr nginx 停止 nginx -s stop 测试配置文件的语法是否有误 nginx -t 重启nginx nginx-s reload

网络安全之动态路由OSPF基础

OSPF&#xff1a;开放式最短路径优先协议。 1、协议使用范围&#xff1a;IGP。 2、协议算法特点&#xff1a;链路状态型路由协议。 3、协议是否传递网络掩码&#xff1a;传递网络掩码&#xff08;无类别的路由协议&#xff09;。 4、协议封装&#xff1a;基于IP协议封装&am…

第六代移动通信介绍、无线网络类型、白皮书

关于6G 即第六代移动通信的介绍&#xff0c; 图解通信原理与案例分析-30&#xff1a;6G-天地互联、陆海空一体、全空间覆盖的超宽带移动通信系统_6g原理-CSDN博客文章浏览阅读1.7w次&#xff0c;点赞34次&#xff0c;收藏165次。6G 即第六代移动通信&#xff0c;6G 将在5G 的基…

《QT实用小工具·六十》Qt 多列时间轴控件

1、概述 源码放在文章末尾 Qt 多列时间轴控件。 可与多段字符串格式自由转换&#xff0c;也可手动添加列表项。 专门用来以时间轴作为事件线发展顺序的故事大纲。 特点 时间背包功能&#xff1a;记录所有物品或属性发生的变化&#xff0c;随时回溯 时间可输入任意内容&…

【区块链】智能合约简介

智能合约起源 智能合约这个术语至少可以追溯到1995年&#xff0c;是由多产的跨领域法律学者尼克萨博&#xff08;NickSzabo&#xff09;提出来的。他在发表在自己的网站的几篇文章中提到了智能合约的理念。他的定义如下&#xff1a;“一个智能合约是一套以数字形式定义的承诺&a…

【C++STL详解(八)】--------stack和queue的模拟实现

目录 前言 一、stack模拟实现 二、queue的模拟实现 前言 前面也介绍了stack和queue的常见接口&#xff0c;我们也知道stack和queue实际上是一种容器适配器&#xff0c;它们只不过是对底层容器的接口进行封装而已&#xff0c;所以模拟实现起来比较简单&#xff01;一起来看看是…

杭州恒生面试,社招,3年经验

你好&#xff0c;我是田哥 一位朋友节前去恒生面试&#xff0c;其实面试问题大部分都是八股文&#xff0c;但由于自己平时工作比较忙&#xff0c;完全没有时间没有精力去看八股文&#xff0c;导致面试结果不太理想&#xff0c;HR说节后通知面试结果&#xff08;估计是凉了&…

北邮22级信通院DSP:实验三(1):FFT变换、IFFT变换(附每步8点变换蝶形图)保姆级讲解+用C++程序实现复数域的FFT变换和IFFT变换

北邮22信通一枚~ 跟随课程进度更新北邮信通院DSP的笔记、代码和文章&#xff0c;欢迎关注~ 获取更多文章&#xff0c;请访问专栏&#xff1a; 北邮22级信通院DSP_青山入墨雨如画的博客-CSDN博客 目录 一、预备知识 1.1 FFT算法 1.2.1由DFT到FFT 1.2.2 基2时域抽选算法 …

华为:三层交换机与路由器连通上网实验

三层交换机是一种网络交换机&#xff0c;可以实现基于IP地址的高效数据转发和路由功能&#xff0c;通常用于大型企业、数据中心和校园网络等场景。此外&#xff0c;三层交换机还支持多种路由协议&#xff08;如OSPF、BGP等&#xff09;&#xff0c;以实现更为复杂的网络拓扑结构…

重装win11系统后找不到WiFi

由于电脑崩溃重装了系统&#xff0c;win11,装完之后WiFi图标不见了且网络适配器根本没有无线网络选项。 右键电脑》管理》网络适配器。 在刚装好系统时候并没有前两项&#xff0c;查了很多资料&#xff0c;比如 关机14s 重启&#xff0c;还有通过服务配置 WLAN AutoConfig 都…

【嵌入式DIY实例】-基于GSM的远程灌溉系统

基于GSM的远程灌溉系统 文章目录 基于GSM的远程灌溉系统1、硬件准备与接线2、软件准备3、代码实现本文将详细介绍如何搭建通过使用手机实现对灌溉系统的远程控制。该系统利用全球移动通信系统(GSM)技术在灌溉系统和移动电话之间建立通信。该系统建立在流行的开源微控制器平台…

IP规划案例

整个OSPF环境IP基于172.16.0.0/16划分 172.16.0.0/16 先分成2个网段&#xff08;OSPF RIP&#xff09;&#xff0c;借1位172.16.0.0/17 ---OSPF 再按区域划分&#xff08;5个区域&#xff09;&#xff0c;借3位 172.16.0.0/20 ---Area 0 三个环回 MGRE 4个网…