代码随想录【Day23】| 669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树

news/2024/3/29 18:33:50/文章来源:https://blog.csdn.net/weixin_42764266/article/details/129194836

669. 修剪二叉搜索树

题目链接

题目描述:
给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。
在这里插入图片描述

难点:

思路:
主要操作和上一题BST中删除根节点的操作类似
但是要注意其他细节:
采用前序遍历,

  1. 需要更新根节点:当根节点(包括更新后的)落在[low, high]区间外,要进行连续删除
    1.1 如果左右子树均为空:直接返回null
    1.2 如果左子树不为空,右子树为空:更新当前根节点为左孩子
    1.3 如果左子树为空,右子树不为空:更新当前根节点为右孩子
    1.4 如果左右子树均不为空:那就调整BST

  2. 不需要更新根节点:递归遍历左、右子树

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) return null;while (root.val < low || root.val > high) { //删除根结点(包括更新后的根节点)if (root.left == null && root.right == null) return null;if (root.left == null && root.right != null) { //更新根节点root = root.right;continue;}if (root.right == null && root.left != null) { //更新根节点root = root.left;continue;}TreeNode tmp = root.right;while (tmp.left != null) {tmp = tmp.left;}tmp.left = root.left;root = root.right;}root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
}

以上是自己敲的

继续精简可以写成↓,哇咔咔,牛的!

//代码随想录参考代码
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;}
}

时长:
20min

收获:
多情况分析


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

题目链接

题目描述:
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:
在这里插入图片描述

难点:

思路:
因为给定数组是有序的,采用二分法进行构造就可以保证BST是平衡的

//左闭右闭[left, right]
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return buildBST(nums, 0, nums.length-1);}public TreeNode buildBST(int[] nums, int left, int right) {if (left > right) return null;int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = buildBST(nums, left, mid-1);root.right = buildBST(nums, mid+1, right);return root;}
}//左闭右开[left, right)
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return buildBST(nums, 0, nums.length);}public TreeNode buildBST(int[] nums, int left, int right) {if (left >= right) return null;int mid = (left+right)/2;TreeNode root = new TreeNode(nums[mid]);root.left = buildBST(nums, left, mid);root.right = buildBST(nums, mid+1, right);return root;}
}

时长:
6min

收获:
二分法复习


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

题目链接

题目描述:
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。

示例 1:
在这里插入图片描述

  • 输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
  • 输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

  • 输入:root = [0,null,1]
  • 输出:[1,null,1]

示例 3:

  • 输入:root = [1,0,2]
  • 输出:[3,3,2]

示例 4:

  • 输入:root = [3,2,4,1]
  • 输出:[7,9,4,10]
    提示:
    树中的节点数介于 0 和 104 之间。
    每个节点的值介于 -104 和 104 之间。
    树中的所有值 互不相同 。
    给定的树为二叉搜索树。

难点:

思路:
根据题目要求以及观察示例
应该采用“右中左”的遍历顺序来构造

class Solution {int curSum;public TreeNode convertBST(TreeNode root) {if (root == null) return null;root.right = convertBST(root.right);curSum += root.val;root.val = curSum;root.left = convertBST(root.left);return root;}
}

时长:
8min

收获:
。。。

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

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

相关文章

Git ---- GitHub 操作

Git ---- GitHub 操作1. 创建远程仓库2. 远程仓库操作1. 创建爱你远程仓库别名2. 推送本地分支到远程仓库3. 克隆远程仓库到本地4. 邀请加入团队5. 拉取远程库内容3. 跨团队协作4. SSH 免密登录GitHub 网址&#xff1a;https://github.com/ Ps&#xff1a;全球最大同性交友网站…

makdown模版参考

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…

RK系列(RK3568) i2s 音频输入 麦克风驱动

平台&#xff1a;Android12SOC&#xff1a;RK3568外围芯片&#xff1a;XS9922i2s简介&#xff1a;从上图看I2s主要的线有&#xff1a;SDO SCLK LRCK MCLK I2S协议只定义三根信号线&#xff1a;串行时钟信号SCLK(BCLK)、数据信号SD和左右声道选择信号WS。&#xff08;1&#xff…

Leetcode力扣秋招刷题路-0103

从0开始的秋招刷题路&#xff0c;记录下所刷每道题的题解&#xff0c;帮助自己回顾总结 103. 二叉树的锯齿形层序遍历 给你二叉树的根节点 root &#xff0c;返回其节点值的 锯齿形层序遍历 。&#xff08;即先从左往右&#xff0c;再从右往左进行下一层遍历&#xff0c;以此…

注意力机制详解系列(一):注意力机制概述

&#x1f468;‍&#x1f4bb;作者简介&#xff1a; 大数据专业硕士在读&#xff0c;CSDN人工智能领域博客专家&#xff0c;阿里云专家博主&#xff0c;专注大数据与人工智能知识分享。 &#x1f389;专栏推荐&#xff1a; 目前在写CV方向专栏&#xff0c;更新不限于目标检测、…

SSM+HTML搭建(小白教学)

最近做项目,觉得还是有意义记录以下前后端框架是怎么搭建的,今天给大家介绍介绍SSM:SpringBootSpringMVCMyBatis后端搭建:SpringBoot快速搭建的网站(Spring Initializr)选择创建之后,会下载到一个zip压缩包,对压缩包进行解压(包地址一般选择后端项目的放的文件夹中)用idea打开项…

上岸16K,薪资翻倍,在华为外包做测试是一种什么样的体验····

现在回过头看当初的决定&#xff0c;还是正确的&#xff0c;自己转行成功&#xff0c;现在进入了华为外包测试岗&#xff0c;脱离了工厂生活&#xff0c;薪资也翻了一倍不止。 我17年毕业于一个普通二本学校&#xff0c;电子信息工程学院&#xff0c;是一个很不出名的小本科。…

字符串匹配--strstr函数的模拟实现思路和代码

一&#xff0c;strstr函数 原型&#xff1a; const char * strstr ( const char * str1, const char * str2 );char * strstr ( char * str1, const char * str2 ); strstr是一个字符串匹配函数&#xff0c;在str1中去寻找str2&#xff0c;如果找到&#xff0c;返回str2在…

Tapdata Connector 实用指南:实时数仓场景之数据实时同步至 ClickHouse

【前言】作为中国的 “Fivetran/Airbyte”, Tapdata 是一个以低延迟数据移动为核心优势构建的现代数据平台&#xff0c;内置 60 数据连接器&#xff0c;拥有稳定的实时采集和传输能力、秒级响应的数据实时计算能力、稳定易用的数据实时服务能力&#xff0c;以及低代码可视化操作…

Tina_Linux_系统软件 开发指南

Tina_Linux_系统软件 开发指南 1 概述 编写目的&#xff1a;本文档作为Allwinner Tina Linux系统平台开发指南&#xff0c;旨在帮助软件开发工程师、技术支持工程师快速上手&#xff0c;熟悉Tina Linux系统的开发及调试流程。 适用范围&#xff1a;Tina Linux v3.5及以上版本…

博客管理系统--项目说明

项目体验地址&#xff08;账号&#xff1a;123&#xff0c;密码&#xff1a;123&#xff09;http://120.53.20.213:8080/blog_system/login.html项目码云Gitee地址&#xff1a;https://gitee.com/GoodManSS/project/tree/master/blog_system&#xff08;一&#xff09;准备工作…

常见前端基础面试题(HTML,CSS,JS)(三)

JS 中如何进行数据类型的转换&#xff1f; 类型转换可以分为两种&#xff0c;隐性转换和显性转换 显性转换 主要分为三大类&#xff1a;数值类型、字符串类型、布尔类型 三大类的原始类型值的转换规则我就不一一列举了 数值类型&#xff08;引用类型转换&#xff09; Numbe…

什么是SSL端口?HTTPS配置技术指南

安全套接字层&#xff08;SSL&#xff09;是负责互联网连接的数据身份验证和加密的技术。它加密在两个系统之间&#xff08;通常在服务器和客户端之间&#xff09;之间通过互联网发送的数据&#xff0c;使其保持私密。随着在线隐私的重要性日益增加&#xff0c;您应该熟悉SSL端…

「RISC-V Arch」SBI 规范解读(上)

术语 SBI&#xff0c;Supervisor Binary Interface&#xff0c;管理二进制接口 U-Mode&#xff0c;User mode&#xff0c;用户模式 S-Mode&#xff0c;Supervisor mode&#xff0c;监督模式 VS-Mode&#xff0c;Virtualization Supervisor mode&#xff0c;虚拟机监督模式 …

电商共享购模式,消费增值返利,app开发

在当今以市场需求为主导的数字经济时代&#xff0c;消费者需求呈现出精细化管理和多元化的特性&#xff0c;目标市场日渐完善&#xff0c;另外在大数据技术迅速进步和运用的驱动下&#xff0c;总体行业的发展节奏感也在不断加速。因而&#xff0c;企业需要建立一套灵活多变的经…

HyperGBM用Adversarial Validation解决数据漂移问题

本文作者&#xff1a;杨健&#xff0c;九章云极 DataCanvas 主任架构师 数据漂移问题近年在机器学习领域来越来越得到关注&#xff0c;成为机器学习模型在实际投产中面对的一个主要挑战。当数据的分布随着时间推移逐渐发生变化&#xff0c;需要预测的数据和用于训练的数据分布…

格雷码的实现

格雷码&#xff1a;任意两个相邻的二进制数之间只有一位不同 想必通信专业的学生应该都接触过格雷码&#xff0c;它出现在数电、通信原理等课程里。 如下图所示一个四位格雷码是什么样子的&#xff1a; 格雷码的特点&#xff1a; 其最大的特点是任意上下相邻的两个码值间&am…

线性数据结构:数组 Array

一、前言数组是数据结构还是数据类型&#xff1f;数组只是个名称&#xff0c;它可以描述一组操作&#xff0c;也可以命名这组操作。数组的数据操作&#xff0c;是通过 idx->val 的方式来处理。它不是具体要求内存上要存储着连续的数据才叫数组&#xff0c;而是说&#xff0c…

内网渗透(五十六)之域控安全和跨域攻击-非约束委派攻击

系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…

Linux下java服务占用cpu过高如何处理

Linux下java服务占用cpu过高如何处理 top命令查看进程信息 top按下shiftp,按cpu使用率排行,可见进程1932占用最高,并且是一个java服务 使用jps命令确认java服务 [rootVM-16-16-centos ~]# jps 1011 Jps 9462 yuan_back-0.0.1-SNAPSHOT.jar 1932 spigot-1.18.jar查找异常进程中…