当前位置: 首页 > news >正文

代码随想录算法训练营| 669. 修剪二叉搜索树 、 108.将有序数组转换为二叉搜索树 、 538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树 

题目

参考文章

思路:这题其实就是删除不符合上下边界的节点。注意:这里删除不符合上下边界节点时,这个不符合上下边界的节点的左或右子树可能存在符合上下边界的节点,所i有每次比较完之后,要继续遍历其左或右子树,直到把所有不符合上下边界的节点都删除为止

代码:

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) {return null;}if (root.val < low) {return trimBST(root.right, low, high); //当当前节点值小于下边界时,就直接继续遍历当前节点的右子树即可,找到符合上下边界的值}if (root.val > high) {//当当前节点值大于上边界时,就直接继续遍历当前节点的左子树即可,找到符合上下边界的值return trimBST(root.left, low, high);}// root在[low,high]范围内//接入如何条件的左右孩子root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
}

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

题目

参考文章

思路:这道题目是构造平衡二叉搜索树,所以我们构造的时候,不能只在节点的某一边构造。因此我们要从数组的中间位置开始构造根节点,我们采用左闭右开的方式。因为是左闭右开,所以非法条件为 left>=right;然后每次取中间数组位置构建值,构建完后又继续构建左右节点

代码:

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length);}public TreeNode sortedArrayToBST(int[] nums, int left, int right) {if (left >= right) {return null;}if (right - left == 1) {//当遍历到当前数组的的下标位置相差1时,表示已经在数组边界,所以直接构建节点返回即可return new TreeNode(nums[left]);}int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = sortedArrayToBST(nums, left, mid);root.right = sortedArrayToBST(nums, mid + 1, right);return root;}
}

538.把二叉搜索树转换为累加树 

题目

参考文章

思路:这题目的意思就是让我们从这个二叉搜索树从大到小遍历,原来左中右的情况是从小到大遍历,所以从大到小遍历就是右中左。了解这个这题目就很好解决了。这里设置一个int sum,用于存储累加值,而且每次累加后,当前记得的值就更新为sum(题目要求),按右中左去遍历即可

代码:

class Solution {int sum;public TreeNode convertBST(TreeNode root) {sum = 0;convertBST1(root);return root;}// 按右中左顺序遍历,累加即可public void convertBST1(TreeNode root) {if (root == null) {return;}convertBST1(root.right);sum += root.val;root.val = sum;convertBST1(root.left);}
}

二叉树总结

在二叉树题目选择什么遍历顺序是不少同学头疼的事情,我们做了这么多二叉树的题目了,Carl给大家大体分分类

  • 涉及到二叉树的构造,无论普通二叉树还是二叉搜索树一定前序,都是先构造中节点。

  • 求普通二叉树的属性,一般是后序,一般要通过递归函数的返回值做计算。

  • 求二叉搜索树的属性,一定是中序了,要不白瞎了有序性了。

注意在普通二叉树的属性中,我用的是一般为后序,例如单纯求深度就用前序,二叉树:找所有路径 (opens new window)也用了前序,这是为了方便让父节点指向子节点。

所以求普通二叉树的属性还是要具体问题具体分析。

相关文章:

代码随想录算法训练营| 669. 修剪二叉搜索树 、 108.将有序数组转换为二叉搜索树 、 538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树 题目 参考文章 思路&#xff1a;这题其实就是删除不符合上下边界的节点。注意&#xff1a;这里删除不符合上下边界节点时&#xff0c;这个不符合上下边界的节点的左或右子树可能存在符合上下边界的节点&#xff0c;所i有每次比较完之后&#xff0c;要继…...

Django模型实现外键自关联

Django模型实现外键自关联 1、场景 省市区、评论 2、模型models.py from django.db import models 资讯评论:资讯,用户,是否取消,时间class CommentInfomation(models.Model):info = models...

Android ViewModel

一问&#xff1a;ViewModel如何保证应用配置变化后能够自动继续存在&#xff0c;其原理是什么&#xff0c;ViewModel的生命周期和谁绑定的? ViewModel 的确能够在应用配置发生变化&#xff08;例如屏幕旋转&#xff09;后继续存在&#xff0c;这得益于 Android 系统的 ViewMod…...

优先算法1--双指针

“一念既出&#xff0c;万山无阻。”加油陌生人&#xff01; 目录 1.双指针--移动零 2.双指针-复写零 ok&#xff0c;首先在学习之前&#xff0c;为了方便大家后面的学习&#xff0c;我们这里需要补充一个知识点&#xff0c;我这里所谓的指针&#xff0c;不是之前学习的带有…...

利用弹性盒子完成移动端布局(第二次实验作业)

需要实现的效果如下&#xff1a; 下面是首先是这个项目的框架&#xff1a; 然后是html页面的代码&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"wid…...

C# 字符串(string)三个不同的处理方法:IsNullOrEmpty、IsInterned 、IsNullOrWhiteSpace

在C#中&#xff0c;string.IsNullOrEmpty、string.IsInterned 和 string.IsNullOrWhiteSpace 是三个不同的字符串处理方法&#xff0c;它们各自有不同的用途&#xff1a; 1.string.IsNullOrEmpty&#xff1a; 这个方法用来检查字符串是否为null或者空字符串&#xff08;"…...

读书笔记 - 虚拟化技术 - 0 QEMU/KVM概述与历史

《QEMU/KVM源码解析与应用》 - 王强 概述 虚拟化简介 虚拟化思想 David Wheeler&#xff1a;计算机科学中任何问题都可以通过增加一个中间层来解决。 虚拟化思想存在与计算机科学的各个领域。 主要思想&#xff1a;通过分层将底层的复杂&#xff0c;难用的资源虚拟抽象为简…...

常见的负载均衡

1.常见的负载均衡服务 负载均衡服务是分布式系统中用于分配网络流量和请求的关键组件&#xff0c;它可以帮助提高应用程序的可用性、可扩展性和响应速度。以下是一些常用的负载均衡服务&#xff1a; Nginx&#xff1a;一个高性能的Web服务器和反向代理&#xff0c;广泛用于实现…...

利用sessionStorage收集用户访问信息,然后传递给后端

这里只是简单的收集用户的停留时间、页面加载时间、当前页面URL及来源页面&#xff0c;以做示例 <html><head><meta http-equiv"content-type" content"text/html; charsetUTF-8"/><title>测试sessionStorage存储用户访问信息<…...

什么是Qseven?模块电脑(核心板)规范标准简介二

1.概念 Qseven是一种通用的、小尺寸计算机模块标准&#xff0c;适用于需要低功耗、低成本和高性能的应用。 Qseven模块电脑&#xff08;核心板&#xff09;采用230Pin金手指连接器 2.Qseven的起源 Qseven最初是由Congatec、SECO、MSC三家欧洲公司于2008年发起&#xff0c;旨在…...

leetcode数组(三)-有序数组的平方

题目 . - 力扣&#xff08;LeetCode&#xff09; 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 例1 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,100] 解释&#…...

HCIP-HarmonyOS Application Developer 习题(五)

1、以下哪种原子化布局能力属于自适应变化能力? A. 拉伸 B.占比 C. 隐藏 D.拆行 答案&#xff1a;A 分析&#xff1a;划分为“自适应变化能力”和“自适应布局能力”两类。 其中&#xff0c;自适应变化能力包含了缩放能力和拉伸能力&#xff0c;自适应布局能力包含了隐藏、折…...

【详细教程】如何使用YOLOv11进行图像与视频的目标检测

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…...

H7-TOOL的LUA小程序教程第14期:任意波形信号发生器,0-20mA输出和微型数控电源(2024-10-11,已更新)

LUA脚本的好处是用户可以根据自己注册的一批API&#xff08;当前TOOL已经提供了几百个函数供大家使用&#xff09;&#xff0c;实现各种小程序&#xff0c;不再限制Flash里面已经下载的程序&#xff0c;就跟手机安装APP差不多&#xff0c;所以在H7-TOOL里面被广泛使用&#xff…...

Redis面试篇3

1、Redis的数据类型&#xff0c;以及每种数据类型的使用场景&#xff1f; 常见的几种数据类型和使用场景如下&#xff1a; 字符串(String)&#xff1a;字符串类型是Redis最基本的数据结构&#xff0c;一个键最大能存储512MB。 使用场景&#xff1a;适用于计数器、分布式锁、缓…...

集成方案 | 借助 Microsoft Copilot for Sales 与 Docusign,加速销售流程!

加速协议信息提取&#xff0c;随时优化邮件内容~ 在当今信息爆炸的时代&#xff0c;销售人员掌握着丰富的数据资源。他们能够通过 CRM 平台、电子邮件、合同库以及其他多种记录系统&#xff0c;随时检索特定个人或组织的关键信息。这些数据对于销售沟通至关重要。然而&#x…...

k8s 1.28.2 集群部署 MinIO 分布式集群

文章目录 [toc]MinIO 介绍MinIO 生产硬件要求MinIO 存储要求MinIO 内存要求MinIO 网络要求MinIO 部署架构分布式 MinIO复制的 MinIO 部署 MinIO创建目录节点打标签创建 namespace创建 pv创建 MinIO配置 ingress问题记录通过代理服务器访问 MinIO 的 Object Browser 界面一直显示…...

HAL库常用的函数:

目录 HAL库&#xff1a; 1.GPIO常用函数&#xff1a; 1.HAL_GPIO_ReadPin( ) 2.HAL_GPIO_WritePin( ) 3.HAL_GPIO_TogglePin( ) 4.HAL_GPIO_EXTI_IRQHandler( ) 5.HAL_GPIO_EXTI_Callback( ) 2.UART常用函数&#xff1a; 1.HAL_U…...

如何捕捉行情爆发的前兆

在金融市场的激烈角逐中&#xff0c;每一次行情的爆发都是投资者获取丰厚回报的关键时刻。然而&#xff0c;如何识别并把握这些时刻&#xff0c;却是一门需要深厚金融专业知识和敏锐洞察力的艺术。今天&#xff0c;我们就来深入探讨行情爆发的初期信号&#xff0c;揭示那些能够…...

【万字长文】Word2Vec计算详解(一)CBOW模型

【万字长文】Word2Vec计算详解&#xff08;一&#xff09;CBOW模型 写在前面 本文用于记录本人学习NLP过程中&#xff0c;学习Word2Vec部分时的详细过程&#xff0c;本文与本人写的其他文章一样&#xff0c;旨在给出Word2Vec模型中的详细计算过程&#xff0c;包括每个模块的计…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...