LeetCode669. 修剪二叉搜索树

669. 修剪二叉搜索树

文章目录

      • [669. 修剪二叉搜索树](https://leetcode.cn/problems/trim-a-binary-search-tree/)
        • 一、题目
        • 二、题解
          • 方法一:递归法
          • 方法二:迭代法


一、题目

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1:

img

输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]

示例 2:

img

输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出:[3,2,null,1]

提示:

  • 树中节点数在范围 [1, 104]
  • 0 <= Node.val <= 104
  • 树中每个节点的值都是 唯一
  • 题目数据保证输入是一棵有效的二叉搜索树
  • 0 <= low <= high <= 104

二、题解

方法一:递归法

我们从根节点开始,逐个遍历树的节点,判断每个节点的值是否在给定的范围内。如果节点的值小于最小值(low),那么我们就需要修剪掉左子树,因为左子树的节点值都会更小,不可能在范围内。类似地,如果节点的值大于最大值(high),就需要修剪掉右子树。如果节点的值在范围内,我们保留这个节点,并分别递归修剪左子树和右子树。

下面是具体的算法思路以及解题步骤:

算法思路

  1. 如果树为空(即根节点为nullptr),直接返回nullptr,因为没有需要修剪的节点。
  2. 如果根节点的值小于最小值low,那么根节点以及左子树的所有节点都会小于low,所以我们需要修剪掉左子树,递归调用trimBST(root->right, low, high),返回修剪后的右子树作为新的根节点。
  3. 如果根节点的值大于最大值high,那么根节点以及右子树的所有节点都会大于high,所以我们需要修剪掉右子树,递归调用trimBST(root->left, low, high),返回修剪后的左子树作为新的根节点。
  4. 如果根节点的值在范围内,我们保留这个节点,并分别递归修剪左子树和右子树,即root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);
  5. 最后返回修剪后的根节点。

具体实现

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return nullptr;if(root->val < low){return trimBST(root->right, low, high);}if(root->val > high){return trimBST(root->left, low, high);}root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};

算法分析

  • 时间复杂度:每个节点都被访问了一次,所以时间复杂度为O(N),其中N是树中的节点数。
  • 空间复杂度:递归调用的栈空间,最坏情况下(树完全不平衡),递归的深度可以达到N,所以空间复杂度为O(N)。
方法二:迭代法

算法思路

  1. 首先,处理根节点为空的情况。如果根节点为空,直接返回 nullptr,因为没有需要修剪的节点。
  2. 然后,我们需要找到新的根节点,它的值应当在范围 [low, high] 内。通过迭代循环,将当前根节点移动到满足条件的位置。如果当前根节点的值小于 low,说明应当修剪掉左子树,所以移动到右子树;如果当前根节点的值大于 high,说明应当修剪掉右子树,所以移动到左子树。
  3. 修剪左子树:从当前根节点开始,遍历到左子树的叶节点(最小值),如果叶节点的值小于 low,则将叶节点的右子树连接到当前叶节点的父节点上,从而删除小于 low 的节点。
  4. 修剪右子树:从当前根节点开始,遍历到右子树的叶节点(最大值),如果叶节点的值大于 high,则将叶节点的左子树连接到当前叶节点的父节点上,从而删除大于 high 的节点。
  5. 最后,返回修剪后的根节点。

具体实现

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (!root) return nullptr;  // 处理根节点为空的情况// 找到新的根节点,值在 [low, high] 范围内while (root && (root->val < low || root->val > high)) {if (root->val < low)root = root->right;elseroot = root->left;}TreeNode *cur = root;// 修剪左子树while (cur && cur->left) {if (cur->left->val < low) {cur->left = cur->left->right;} else {cur = cur->left;}}cur = root;// 修剪右子树while (cur && cur->right) {if (cur->right->val > high) {cur->right = cur->right->left;} else {cur = cur->right;}}return root;}
};

算法分析

  • 时间复杂度:这个解法的时间复杂度取决于两个遍历操作。第一个遍历操作在找到新的根节点时,最多访问树中所有节点,所以是 O(N)。第二个和第三个遍历操作在修剪左右子树时,最多访问树中所有节点,也是 O(N)。综合起来,总的时间复杂度是 O(N)。
  • 空间复杂度:这个解法没有使用额外的数据结构来存储中间结果,只使用了几个辅助变量,所以空间复杂度是 O(1)。

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

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

相关文章

使用秘籍|如何实现图数据库 NebulaGraph 的高效建模、快速导入、性能优化

本文整理自 NebulaGraph PD 方扬在「NebulaGraph x KubeBlocks」meetup 上的演讲&#xff0c;主要包括以下内容&#xff1a; NebulaGraph 3.x 发展历程NebulaGraph 最佳实践 建模篇导入篇查询篇 NebulaGraph 3.x 的发展历程 NebulaGraph 自 2019 年 5 月开源发布第一个 alp…

opencv进阶19-基于opencv 决策树cv::ml::DTrees 实现demo示例

opencv 中创建决策树 cv::ml::DTrees类表示单个决策树或决策树集合&#xff0c;它是RTrees和 Boost的基类。 CART是二叉树&#xff0c;可用于分类或回归。对于分类&#xff0c;每个叶子节点都 标有类标签&#xff0c;多个叶子节点可能具有相同的标签。对于回归&#xff0c;每…

【Acwing291】蒙德里安的梦想(状态压缩dp)详细讲解

题目描述 题目分析 显而易见的重要事实 首先&#xff0c;需要明白一个很重要的事实&#xff1a; 所有的摆放方案数所有横着摆放且合理的方案数 这是因为&#xff0c;横着的确定之后&#xff0c;竖着的一定会被唯一确定&#xff0c;举一个例子&#xff1a; ------唯一确定-…

RabbitMQ---订阅模型-Fanout

1、 订阅模型-Fanout Fanout&#xff0c;也称为广播。 流程图&#xff1a; 在广播模式下&#xff0c;消息发送流程是这样的&#xff1a; 1&#xff09; 可以有多个消费者 2&#xff09; 每个消费者有自己的queue&#xff08;队列&#xff09; 3&#xff09; 每个队列都要绑定…

Windows 10【压缩卷】操作报错【无法将卷压缩到超出任何不可移动的文件所在的点】的解决方法

目录 一、背景 二、原因 三、解决方法 3.1 Windows自带的碎片清理工具 3.1.1 操作步骤 3.1.2 操作结果 3.2 MyDefrag工具清理磁盘碎片 3.2.1 操作步骤 3.2.2 操作结果 3.3 Windows自带的事件查看器 3.3.1 操作步骤 3.3.2 操作结果 3.4 关闭虚拟内存并删除虚拟内存…

离谱事件解决方法2 无法定位程序输入点XXX于动态链接库XXX.dll

事情经过&#xff1a; 本人一只acmer&#xff0c;使用sublime编写代码&#xff0c;但是前两天在打开cpp类型的文件的时候显示报错如下&#xff1a; 这里的dll文件就是动态链接库&#xff0c;它并不是一个可执行文件&#xff0c;里面存放的是程序的函数实现过程&#xff08;公用…

django+MySQL计算机毕设之图片推荐系统(报告+源码)

图片推荐系统是在的数据存储主要通过MySQL。用户在使用应用时产生的数据通过Python语言传递给数据库。通过此方式促进图片推荐信息流动和数据传输效率&#xff0c;提供一个内容丰富、功能多样、易于操作的平台。述了数据库的设计&#xff0c;系统的详细设计部分主要论述了几个主…

Ubuntu释放VMware虚拟磁盘未使用空间

By: Ailson Jack Date: 2023.08.26 个人博客&#xff1a;http://www.only2fire.com/ 本文在我博客的地址是&#xff1a;http://www.only2fire.com/archives/152.html&#xff0c;排版更好&#xff0c;便于学习&#xff0c;也可以去我博客逛逛&#xff0c;兴许有你想要的内容呢。…

面试之快速学习计算机网络-http

1. HTTP常见状态码 2. 3开头重定向&#xff0c;4开头客户端错误&#xff0c;5开头服务端错误 2. HTTP 报文 1. start-line&#xff1a;请求行&#xff0c;可以为以下两者之一&#xff1a; 请求行&#xff1a; GET /hello-world2.html HTTP/1.1状态行&#xff1a;HTTP/1.1 200…

YOLOv8教程系列:三、K折交叉验证——让你的每一份标注数据都物尽其用(yolov8目标检测+k折交叉验证法)

YOLOv8教程系列&#xff1a;三、K折交叉验证——让你的每一份标注数据都物尽其用&#xff08;yolov8目标检测k折交叉验证法&#xff09; 0.引言 k折交叉验证&#xff08;K-Fold Cross-Validation&#xff09;是一种在机器学习中常用的模型评估技术&#xff0c;用于估计模型的性…

JavaScript(笔记)

目录 Hello World JavaScript 的变量 JavaScript 动态类型 隐式类型转换 JavaScript 数组 JavaScript 函数 JavaScript 中变量的作用域 对象 DOM 选中页面元素 事件 获取 / 修改元素内容 获取 / 修改元素属性 获取 / 修改 表单元素属性 获取 / 修改样式属性 新…

Java版B/S架构 智慧工地源码,PC、移动、数据可视化智慧大屏端源码

智慧工地是什么&#xff1f;智慧工地主要围绕绿色施工、安全管控、劳务管理、智能管理、集成总控等方面&#xff0c;帮助工地解决运营、管理方面各个难点痛点。在互联网的加持下促进项目现场管理的创新与发展&#xff0c;实现工程管理人员与工程施工现场的整合&#xff0c;构建…

[机缘参悟-102] :IT人 - 管理的本质?管理人与从事技术的本质区别?人性、冰山模型、需求层次模型

感悟&#xff1a; 管理的本质是&#xff1a;学习各种管理理论、方法、技能&#xff0c;克服自身的人性缺点、预防他人人性的恶点、利用他人的人性特点拿到结果&#xff0c;从而完成组织、管理者的上司、管理者自身、管理者下属的目标。管理中的问题&#xff0c;80%以上都人性问…

rtmp直播

技术要求&#xff1a;nginxnginx-rtmpffmpegVLC 跟着大佬走的&#xff1a; 传送门 准备工作&#xff1a; 首先需要一台公网ip的服务器 这是使用天翼云的弹性云主机&#xff1a;免费试用1个月 天翼云官网 点击关机&#xff0c;更多里面选择重置密码&#xff0c; 默认用户名为…

根据案例写PLC程序-红绿灯控制

案例&#xff1a; 1、南北方向红灯点亮30s后熄灭&#xff1b; 2、在点亮南北方向红灯的同时点亮东西方向绿灯&#xff0c;并在点亮25s后&#xff0c;以0.5s熄灭0.5s点亮的时间闪烁3次后熄灭&#xff1b; 3、在东西方向绿灯熄灭后&#xff0c;东西方向黄灯点亮2s后熄灭&#xff…

数据库的增量备份与差异备份

在当今数字时代&#xff0c;数据已经成为公司的主要资产。为了维护这些珍贵的数据&#xff0c;公司通常会采取各种数据保护措施&#xff0c;其中增量备份是一种很有效的方法。本文将详细介绍什么是数据库的增量备份&#xff0c;以及如何帮助企业更有效地维护数据。  我们需要…

HTML+CSS 查漏补缺

目录 1&#xff0c;HTML1&#xff0c;尺寸的百分比1&#xff0c;普通元素2&#xff0c;绝对&#xff08;固定&#xff09;定位元素3&#xff0c;常见百分比 2&#xff0c;form 表单元素1&#xff0c;form2&#xff0c;button3&#xff0c;label4&#xff0c;outline5&#xff0…

Multisim软件安装包分享(附安装教程)

目录 一、软件简介 二、软件下载 一、软件简介 Multisim软件是一款电路仿真和设计软件&#xff0c;由美国国家仪器公司&#xff08;National Instruments&#xff09;开发。它提供了一个交互式的图形界面&#xff0c;使用户能够轻松地构建和仿真电路。以下是Multisim软件的详…

《扩散模型 从原理到实战》Hugging Face (一)

文章目录 前言第一章 扩散模型简介1.1 扩散模型的原理1.1.1 生成模型1.1.2 扩散过程 前言 Hugging Face最近出版了第一本中文书籍《扩散模型 从原理到实战》&#xff0c;其中内容关于扩散模型&#xff08;Diffusion Model&#xff09;&#xff0c;和AIGC相关的内容较多&#x…

2023企业网盘产品排行榜揭晓:选择最适合你的企业网盘工具

企业网盘产品已成为企业文件管理协作的主要选择之一&#xff0c;无论是在文件管理方面&#xff0c;还是团队协作上&#xff0c;企业网盘都表现优秀。为了帮助企业选到心怡的企业网盘产品&#xff0c;我们综合了不同的产品测评网站意见&#xff0c;整理了2023企业网盘产品排行榜…