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

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

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

收获:
。。。

相关文章:

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

669. 修剪二叉搜索树 题目链接 题目描述&#xff1a; 给定一个二叉搜索树&#xff0c;同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树&#xff0c;使得所有节点的值在[L, R]中 (R>L) 。你可能需要改变树的根节点&#xff0c;所以结果应当返回修剪好的二叉搜索树的新…...

Wsl2 ubuntu 配置git 阿里云codeup

目录 创建一个跟你windows git使用相同的用户名,特别重要 配置git 用户名和邮箱 配置阿里云codeup 拉取仓库提示文件权限问题 给用户目录权限 配置项目文件别名 key_load_public: invalid format 怎么办&#xff1f; WSL ubuntu sshd: no hostkeys available -- exiting…...

展会邀约 | 昂视与您相约BTF第12届上海锂电展

BTF第12届上海国际新能源锂电展将于3月7日在上海新国际博览中心举办。此次展会以“锂想动力&#xff0c;共创未来”为主题&#xff0c;汇聚行业内一众翘楚企业与专业观众&#xff0c;为各位展商以及观众提供专业的锂电交流平台&#xff0c;了解与碰撞新产品、新技术与解决方案&…...

RK3568平台开发系列讲解(驱动基础篇)中断子系统框架

🚀返回专栏总目录 文章目录 一、中断硬件的组成二、软件框架三、中断常见概念沉淀、分享、成长,让自己和他人都能有所收获!😄 📢中断是指 CPU 正常运行期间,由于内外部事件或程序预先安排的事件,引起的 CPU 暂时停止正在运行的程序, 转而为该内部或外部预先安排的事…...

消费复苏迎“春”暖,服装行业如何开启“狂飙”模式?

2023年开年前2个月&#xff0c;全国多地消费市场的“热度”一直在持续上涨&#xff0c;商场、餐馆、娱乐场所等消费市场人气旺盛&#xff0c;消费复苏的“暖”意十足&#xff0c;一幕幕“忙”起来、“热”起来的场景&#xff0c;让各行各业的商家都对未来充满了期待与信心。在消…...

Springboot 整合Flowable工作流框架搭建

我们在开发自动化办公软件时经常会遇到各种审批流程功能&#xff0c;这个使用就需要使用到工作流引擎。目前主流的工作流引擎有Activiti、Flowable、camunda&#xff0c;其中Flowable是在Activiti的基础上开发出来的&#xff0c;基于BPMN2.0协议&#xff0c;它包括 BPMN&#x…...

ASE0510SH-ASEMI的MOS管ASE0510SH

编辑-Z ASE0510SH在SOT-89封装里的静态漏极源导通电阻&#xff08;RDS(ON)&#xff09;为140mΩ&#xff0c;是一款N沟道中低压MOS管。ASE0510SH的最大脉冲正向电流ISM为15A&#xff0c;零栅极电压漏极电流(IDSS)为1uA&#xff0c;其工作时耐温度范围为-55~150摄氏度。ASE0510…...

Golang学习Day2

Go语言中的函数go语言中函数特性go语言有三种函数&#xff1a;普通函数、匿名函数&#xff08;没有名称的函数&#xff09;方法&#xff08;定义在struct上的函数&#xff09;。receivergo语言中不运算函数重载&#xff08;overload&#xff09;&#xff0c;也就是说不允许函数…...

Android 中malloc_debug 原理详解

版本基于&#xff1a;Android R 0. 前言 最近上项目中遇到一个native 可能内存泄漏的问题&#xff0c;曾考虑使用HWASAN&#xff0c;但这个工具是针对整个系统&#xff0c;运行代价还是很高的。而笔者遇到的问题大致有所方向&#xff0c;能指定到某一个进程&#xff0c;针对单…...

D. Triangle Coloring【组合数学,乘法逆元】

链接 分析 题目要求我们去求出最优的染色的方法数。首先什么时候是最优的&#xff0c;这里只有两种颜色&#xff0c;不可能取到三条边&#xff0c;即蓝色为B&#xff0c;红色为R&#xff0c;有BBB,RRR,BBR,RRB四种组合&#xff0c;显然最多的就是取两条边&#xff0c;我们想取到…...

【读论文】AttentionFGAN

【读论文】AttentionFGAN介绍网络架构提取红外图像目标信息的网络辨别器损失函数生成器损失函数辨别器损失函数总结参考论文&#xff1a; https://ieeexplore.ieee.org/document/9103116/如有侵权请联系博主介绍 好久没有读过使用GAN来实现图像融合的论文了&#xff0c;正好看…...

ClickHouse 配置文件使用说明

本文主要介绍 ClickHouse 的配置文件。在 ClickHouse 中配置主要分为两类&#xff0c;一类是负责 server 端配置的&#xff0c;另一类是负责用户端配置的。负责 server 端配置的一般会放在 config.xml 文件中&#xff0c;负责用户端配置的一般会放在 users.xml 文件中。当然如果…...

如果不是互联网人,谁会找到这些神器?

一、上线啦 你肯定该问了&#xff0c;这个是什么鬼东西。它本来是一个创建自己网站的网站。 现在使用它可以创建自己的小程序&#xff0c;又不是有点小厉害了。 而且功能强大&#xff0c;还支持微信支付&#xff0c;分销&#xff0c;优惠券&#xff0c;营销等多种功能。 还有多…...

Neo4j优化

使用参数 查询参数 :params设置参数 :param actorName: Tom Hanks参数的冒号后要用空格使用参数用 $ MATCH (p:Person)-[:ACTED_IN]->(m:Movie) WHERE p.name $actorName RETURN m.released AS releaseDate,m.title AS title ORDER BY m.released DESC多个参数 MATCH (p:Pe…...

CF1692G 2^Sort 题解

CF1692G 2^Sort 题解题目链接字面描述题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码实现题目 链接 https://www.luogu.com.cn/problem/CF1692G 字面描述 题面翻译 给你一个长度为 n(∑n<2⋅105)n \ (\sum n < 2\cdot 10^5)n (∑n<…...

关于物理像素,逻辑像素,像素比

关于物理像素、逻辑像素&#xff08;css像素&#xff09;、分辨率、像素比的超详细讲解 在日常生活中&#xff0c;有这样一个问题。同样的图片为什么在不同的设备上显示的大小是不一样的。&#x1f912;带着这个问题来说明一下。 一、物理像素 设备刚生产出来就已经固定了&a…...

JavaSE基础部分总结

JavaSe基础部分 文章目录JavaSe基础部分1.命名规范2.基本的数据类型3.方法3.1方法的基本格式3.2 方法的分类3.3 方法的注释4.数组4.1 数组的命名格式4.2 数组中存在的址交换的操作4.3数组Arrays常用的方法1. Arrays.asList(数组作为参数或者数据作为参数)&#xff1a;2.Arrays.…...

C++基础知识

目录类和对象C static_cast、dynamic_cast、const_cast和reinterpret_cast1、为什么要引入这四种类型转化&#xff1f;2、应用场景。C/C类型转换的本质struct和class的区别为什么会诞生面向对象的编程思想析构函数的执行时机初始化 const 成员变量C const对象&#xff08;常对象…...

2023/2/24 图数据库Neo4j的理解与应用

1 什么是图数据库&#xff08;graph database&#xff09; 十大应用案例&#xff1a;https://go.neo4j.com/rs/710-RRC-335/images/Neo4j-Top-Use-Cases-ZH.pdf “大数据”每年都在增长&#xff0c;但如今的企业领导者不仅需要管理更大规模的数据&#xff0c;还迫切需要从现有…...

适合视力障碍者的Linux

导读有哪些最适合视障用户的 Linux 发行版&#xff1f;让我们一起来看看。 如果有人视力障碍或失明&#xff0c;他们可能会依赖声音提示或其他交互方式&#xff08;如盲文&#xff09;来阅读和交流。 他们怎样才能使用 Linux 发行版&#xff1f; 嗯&#xff0c;一般来说&…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

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

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

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...