【算法训练营Day18】二叉树part8

文章目录

  • 修剪二叉搜索树
  • 将有序数组转换为二叉搜索树
  • 把二叉搜索树转换为累加树

修剪二叉搜索树

题目链接:669. 修剪二叉搜索树

解题逻辑:

因为在删除的同时要保证相对结构,所以我们不能沿用上一篇文章中的删除逻辑,新的删除逻辑为:

  • 如果是叶子节点且不在范围内,直接删除
  • 如果该节点值小于最小值,则返回该节点的右子树(因为右子树大于最小值,此时右子树中不符合条件的值已经被删除了)
  • 如果该节点值大于最大值,则返回该节点的左子树(因为左子树小于最大值,此时左子树中不符合条件的值已经被删除了)

代码如下:

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null) return null;TreeNode left = trimBST(root.left,low,high);TreeNode right = trimBST(root.right,low,high);if(root.val < low || root.val > high) {if(left == null && right == null) return null;else if(root.val < low) return right;else if(root.val > high) return left;}root.left = left;root.right = right;return root;}
}

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

题目链接:108. 将有序数组转换为二叉搜索树

本题是根据一个有序数组创建一个平衡的二叉搜索树,核心思想就是:将数组从nums.length / 2开始切分,nums.length / 2索引对应的数值作为当前节点的值,左边的为左子树的节点值、右边为右子树的节点值。这样递归切分构造,最后得到的一定是一个平衡的二叉搜索树。

代码如下:

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length == 0) return null;int devide = nums.length / 2;TreeNode left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, devide));TreeNode right;if(devide + 1 >= nums.length) right = sortedArrayToBST(new int[0]);else right = sortedArrayToBST(Arrays.copyOfRange(nums, devide + 1, nums.length));TreeNode node = new TreeNode(nums[devide]);node.left = left;node.right = right;return node;}
}

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

题目链接:538. 把二叉搜索树转换为累加树

解题逻辑:

我们直接使用中序遍历是从小到大遍历,此时数值不好做累加(因为后面的值我们都不知道)。所以我们可以将整个二叉搜索树进行翻转,然后再使用中序遍历修改节点,此时是从大到小遍历,累加值是已知的,所以节点的值更好累加。构造完之后,再翻转一次还原即可。

代码如下:

class Solution {int num = 0;public TreeNode convertBST(TreeNode root) {reverseBST(root);changeBST(root);reverseBST(root);return root;}public void changeBST(TreeNode root){if(root == null) return;changeBST(root.left);int history = root.val;root.val += num;num += history;changeBST(root.right);}public void reverseBST(TreeNode root){if(root == null) return;reverseBST(root.left);reverseBST(root.right);TreeNode temp = root.left;root.left = root.right;root.right = temp;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C++篇】“内存泄露”的宝藏手段:智能指针

目录 智能指针的使用场景分析 RAII和智能指针的设计思路 C标准库智能指针的使用 auto_ptr的使用&#xff1a; unique_ptr的使用&#xff1a; shared_ptr的使用&#xff1a; 模拟shared_ptr: 定制删除器&#xff1a; shared_ptr的循环引用 weak_ptr 智能指针的使用场景…

【密码学】4. 分组密码

目录分组密码分组密码概述Feistel 密码结构数据加密标准&#xff08;DES&#xff09;差分密码分析与线性密码分析分组密码的运行模式国际数据加密算法&#xff08;IDEA&#xff09;高级加密标准&#xff08;AES&#xff0c;Rijndael&#xff09;中国商用密码 SM4祖冲之密码&…

单片机(STM32-WIFI模块)

一、WIFI模块介绍 1. ESP12-F模组介绍 1.1 简介 ESP12-F模组&#xff08;安信可&#xff08;Ai-Thinker&#xff09;ESP8266系列模组&#xff09;是一款基于乐鑫&#xff08;Espressif&#xff09;公司ESP8266芯片的Wi-Fi无线通信模块&#xff0c;广泛应用于物联网&#xff0…

PyTorch 数据类型和使用

关于PyTorch的数据类型和使用的学习笔记 系统介绍了PyTorch的核心数据类型Tensor及其应用。Tensor作为多维矩阵数据容器&#xff0c;支持0-4维数据结构&#xff08;标量到批量图像&#xff09;&#xff0c;并提供了多种数值类型&#xff08;float32/int64等&#xff09;。通过…

[python刷题模板] LogTrick

[python刷题模板] LogTrick 一、 算法&数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码1. 特定或值的最短子数组2. 找特定值3. 找位置j的最后一次被谁更新4. 问某个或和的数量三、其他四、更多例题五、参考链接一、 算法&数据结构 1. 描述 LogTric…

Vim与VS Code

Vim is a clone, with additions, of Bill Joys vi text editor program for Unix. It was written by Bram Moolenaar based on source for a port of the Stevie editor to the Amiga and first released publicly in 1991.其实这个本身不是 IDE &#xff08;只有在加入和配置…

[2025CVPR-图象分类方向]CATANet:用于轻量级图像超分辨率的高效内容感知标记聚合

​1. 研究背景与动机​ ​问题​&#xff1a;Transformer在图像超分辨率&#xff08;SR&#xff09;中计算复杂度随空间分辨率呈二次增长&#xff0c;现有方法&#xff08;如局部窗口、轴向条纹&#xff09;因内容无关性无法有效捕获长距离依赖。​现有局限​&#xff1a; SPI…

课题学习笔记3——SBERT

1 引言在构建基于知识库的问答系统时&#xff0c;"语义匹配" 是核心难题 —— 如何让系统准确识别 "表述不同但含义相同" 的问题&#xff1f;比如用户问 "对亲人的期待是不是欲&#xff1f;"&#xff0c;系统能匹配到知识库中 "追名逐利是欲…

在Word和WPS文字中把全角数字全部改为半角

大部分情况下我们在Word或WPS文字中使用的数字或标点符号都是半角&#xff0c;但是有时不小心按错了快捷键或者点到了输入法的全角半角切换图标&#xff0c;就输入了全角符号和数字。不用担心&#xff0c;使用它们自带的全角、半角转换功能即可快速全部转换回来。一、为什么会输…

数据结构的基本知识

一、集合框架1、什么是集合框架Java集合框架(Java Collection Framework),又被称为容器(container),是定义在java.util包下的一组接口(interfaces)和其实现类(classes).主要表现为把多个元素(element)放在一个单元中,用于对这些元素进行快速、便捷的存储&#xff08;store&…

WebStack-Hugo | 一个静态响应式导航主题

WebStack-Hugo | 一个静态响应式导航主题 #10 shenweiyan announced in 1.3-折腾 WebStack-Hugo | 一个静态响应式导航主题#10 ​编辑shenweiyan on Oct 23, 2023 6 comments 7 replies Return to top shenweiyan on Oct 23, 2023 Maintainer Via&#xff1a;我给自己…

01 基于sklearn的机械学习-机械学习的分类、sklearn的安装、sklearn数据集、数据集的划分、特征工程中特征提取与无量纲化

文章目录机械学习机械学习分类1. 监督学习2. 半监督学习3. 无监督学习4. 强化学习机械学习的项目开发步骤scikit-learn1 scikit-learn安装2 sklearn数据集1. sklearn 玩具数据集鸢尾花数据集糖尿病数据集葡萄酒数据集2. sklearn现实世界数据集20 新闻组数据集3. 数据集的划分特…

携全双工语音通话大模型亮相WAIC,Soul重塑人机互动新范式

近日&#xff0c;WAIC 2025在上海隆重开幕。作为全球人工智能领域的顶级盛会&#xff0c;本届WAIC展览聚焦底层能力的演进与具体垂类场景的融合落地。坚持“模应一体”方向、立足“AI社交”的具体场景&#xff0c;Soul App此次携最新升级的自研端到端全双工语音通话大模型亮相&…

第2章 cmd命令基础:常用基础命令(1)

Hi~ 我是李小咖&#xff0c;主要从事网络安全技术开发和研究。 本文取自《李小咖网安技术库》&#xff0c;欢迎一起交流学习&#x1fae1;&#xff1a;https://imbyter.com 本节介绍的命令有目录操作&#xff08;cd&#xff09;、清屏操作&#xff08;cls&#xff09;、设置颜色…

Java 10 新特性解析

Java 10 新特性解析 文章目录Java 10 新特性解析1. 引言2. 本地变量类型推断&#xff08;JEP 286&#xff09;2.1. 概述2.2. 使用场景2.3. 限制2.4. 与之前版本的对比2.5. 风格指南2.6. 示例代码2.7. 优点与注意事项3. 应用程序类数据共享&#xff08;JEP 310&#xff09;3.1. …

【WRF工具】服务器中安装编译GrADS

目录 安装编译 GrADS 所需的依赖库 conda下载库包 安装编译 GrADS 编译前检查依赖可用性 安装编译 GrADS 参考 安装编译 GrADS 所需的依赖库 以统一方式在 $HOME/WRFDA_LIBS/grads_deps 下安装所有依赖: # 选择一个目录用于安装所有依赖库 export DIR=$HOME/WRFDA_LIBS库包1…

数据结构之队列(C语言)

1.队列的定义&#xff1a; 队列&#xff08;Queue&#xff09;是一种基础且重要的线性数据结构&#xff0c;遵循先进先出&#xff08;FIFO&#xff09;​​ 原则&#xff0c;即最早入队的元素最先出队&#xff0c;与栈不同的是出队列的顺序是固定的。队列具有以下特点&#xff…

C#开发基础之深入理解“集合遍历时不可修改”的异常背后的设计

前言 欢迎关注【dotnet研习社】&#xff0c;今天我们聊聊一个基础问题“集合已修改&#xff1a;可能无法执行枚举操作”背后的设计。 在日常 C# 开发中&#xff0c;我们常常会操作集合&#xff08;如 List<T>、Dictionary<K,V> 等&#xff09;。一个新手开发者极…

【工具】图床完全指南:从选择到搭建的全方位解决方案

前言 在数字化内容创作的时代&#xff0c;图片已经成为博客、文档、社交媒体等平台不可或缺的元素。然而&#xff0c;如何高效、稳定地存储和分发图片资源&#xff0c;一直是内容创作者面临的重要问题。图床&#xff08;Image Hosting&#xff09;作为专门的图片存储和分发服务…

深度学习篇---PaddleDetection模型选择

PaddleDetection 是百度飞桨推出的目标检测开发套件&#xff0c;提供了丰富的模型库和工具链&#xff0c;覆盖从轻量级移动端到高性能服务器的全场景需求。以下是核心模型分类、适用场景及大小选择建议&#xff08;通俗易懂版&#xff09;&#xff1a;一、主流模型分类及适用场…