C++力扣题目669--修剪二叉搜索树

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

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

示例 1:

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

示例 2:

输入: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

 

思路

相信看到这道题目大家都感觉是一道简单题(事实上leetcode上也标明是简单)。

但还真的不简单!

#递归法

直接想法就是:递归处理,然后遇到 root->val < low || root->val > high 的时候直接return NULL,一波修改,赶紧利落。

不难写出如下代码:

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

然而[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的,还要考虑节点0的右子树

我们在重新关注一下第二个示例,如图:

669.修剪二叉搜索树

所以以上的代码是不可行的!

从图中可以看出需要重构二叉树,想想是不是本题就有点复杂了。

其实不用重构那么复杂。

在上图中我们发现节点0并不符合区间要求,那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了(就是把节点0从二叉树中移除),如图:

669.修剪二叉搜索树1

理解了最关键部分了我们再递归三部曲:

  • 确定递归函数的参数以及返回值

这里我们为什么需要返回值呢?

因为是要遍历整棵树,做修改,其实不需要返回值也可以,我们也可以完成修剪(其实就是从二叉树中移除节点)的操作。

但是有返回值,更方便,可以通过递归函数的返回值来移除节点。

这样的做法在二叉树:搜索树中的插入操作 (opens new window)和二叉树:搜索树中的删除操作 (opens new window)中大家已经了解过了。

代码如下:

TreeNode* trimBST(TreeNode* root, int low, int high)

  • 确定终止条件

修剪的操作并不是在终止条件上进行的,所以就是遇到空节点返回就可以了。

if (root == nullptr ) return nullptr;

  • 确定单层递归的逻辑

如果root(当前节点)的元素小于low的数值,那么应该递归右子树,并返回右子树符合条件的头结点。

代码如下:

if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点return right;
}

如果root(当前节点)的元素大于high的,那么应该递归左子树,并返回左子树符合条件的头结点。

代码如下:

if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点return left;
}

接下来要将下一层处理完左子树的结果赋给root->left,处理完右子树的结果赋给root->right。

最后返回root节点,代码如下:

root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;

此时大家是不是还没发现这多余的节点究竟是如何从二叉树中移除的呢?

在回顾一下上面的代码,针对下图中二叉树的情况:

669.修剪二叉搜索树1

如下代码相当于把节点0的右孩子(节点2)返回给上一层,

if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点return right;
}

然后如下代码相当于用节点3的左孩子 把下一层返回的 节点0的右孩子(节点2) 接住。

root->left = trimBST(root->left, low, high);

此时节点3的左孩子就变成了节点2,将节点0从二叉树中移除了。

最后整体代码如下:

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr ) return nullptr;if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点return right;}if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点return left;}root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子return root;}
};

精简之后代码如下:

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;}
};

只看代码,其实不太好理解节点是如何移除的,这一块大家可以自己再模拟模拟!

#迭代法

因为二叉搜索树的有序性,不需要使用栈模拟递归的过程。

在剪枝的时候,可以分为三步:

  • 将root移动到[L, R] 范围内,注意是左闭右闭区间
  • 剪枝左子树
  • 剪枝右子树

代码如下:

class Solution {
public:TreeNode* trimBST(TreeNode* root, int L, int R) {if (!root) return nullptr;// 处理头结点,让root移动到[L, R] 范围内,注意是左闭右闭while (root != nullptr && (root->val < L || root->val > R)) {if (root->val < L) root = root->right; // 小于L往右走else root = root->left; // 大于R往左走}TreeNode *cur = root;// 此时root已经在[L, R] 范围内,处理左孩子元素小于L的情况while (cur != nullptr) {while (cur->left && cur->left->val < L) {cur->left = cur->left->right;}cur = cur->left;}cur = root;// 此时root已经在[L, R] 范围内,处理右孩子大于R的情况while (cur != nullptr) {while (cur->right && cur->right->val > R) {cur->right = cur->right->left;}cur = cur->right;}return root;}
};

#总结

修剪二叉搜索树其实并不难,但在递归法中大家可看出我费了很大的功夫来讲解如何删除节点的,这个思路其实是比较绕的。

最终的代码倒是很简洁。

如果不对递归有深刻的理解,这道题目还是有难度的!

本题我依然给出递归法和迭代法,初学者掌握递归就可以了,如果想进一步学习,就把迭代法也写一写

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

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

相关文章

Uncaught ReferenceError: videojs is not defined

项目场景&#xff1a; 项目背景&#xff1a; 开发 vue 项目时&#xff0c;调试时浏览器前端控制台 出现红色 报错信息&#xff1a; Uncaught ReferenceError: videojs is not defined 问题描述 遇到的问题&#xff1a; 开发 vue 项目时&#xff0c; 浏览器控制台出现如下所…

【Linux】shell 脚本入门详解

一、shell入门简介 1.1什么是shell # 什么是shell网上有很多shell的概念介绍&#xff0c;其实都很官方化&#xff0c;如果你对linux命令很熟悉&#xff0c;那么编写shell就不是一个难事&#xff0c;shell本质上是linux命令&#xff0c;一条一条命令组合在一起&#xff0c;实现…

如何通过内网穿透实现公网访问Portainer管理监控Docker容器

文章目录 前言1. 部署Portainer2. 本地访问Portainer3. Linux 安装cpolar4. 配置Portainer 公网访问地址5. 公网远程访问Portainer6. 固定Portainer公网地址 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风…

Win10专业版系统搭建DNS解析服务

Win10专业版 纯新手&#xff0c;也没弄过Linux的。不喜勿喷&#xff0c;有问题请指出 第一天一头雾水整了几个小时没结果&#xff0c;第二天豁然开朗&#xff0c;10分钟明白了第一天的问题所在。 Win10 安卓&#xff1a; iOS&#xff1a; 搭建DNS服务器的意义&#xff1a; 屏蔽…

MyBatis-Plus 入门指南:安装与配置、代码生成、综合案例、主键生成策略、自动填充

目录 1.MyBatis-Plus介绍 1.1.简介 1.2.特性 1.3.结构 1.4.支持数据库 2.快速开始 3.安装与配置 4.代码生成 5.综合案例 5.1.主键生成策略 5.2.自动填充 1.MyBatis-Plus介绍 1.1.简介 MyBatis-Plus&#xff08;简称 MP&#xff09;是一个 MyBatis 的增强工具&…

写点东西《 Kickstart:搭建 JS 项目的最快方式!》

写点东西《&#x1f680; Kickstart&#xff1a;搭建 JS 项目的最快方式&#xff01;》 如何使用它&#xff1f; 想象一下&#xff1a;你刚刚有一个新的项目创意&#xff0c;你对创意充满热情&#xff0c;并准备好编码。 但是&#xff0c;在实际编写代码之前&#xff0c;您必须…

解决jmeter响应乱码的问题

HTTP请求响应乱码 方法一&#xff1a;添加后置处理器BeanShell PostProcessor&#xff0c;写入【prev.setDataEncoding("utf-8")】 方法二&#xff1a;修改bin目录下的配置文件jmeter.properties&#xff0c;将配置修改为【sampleresult.default.encodingUTF-8】 J…

2024年如何成为技术创作KOL?| 分享抽龙年公仔

引言 2024 年已经到来&#xff0c;你年初的 Flag 立好了吗&#xff1f;今年要创作多少篇文章&#xff1f;要如何获得更大的影响力&#xff1f;如何通过创作来改变自己的职业轨道&#xff1f;你有没有想过&#xff0c;其实成为技术创作领域的一位 KOL&#xff0c;离你并不遥远&a…

2023年全国职业院校技能大赛软件测试赛题—单元测试卷⑤

单元测试 一、任务要求 题目1&#xff1a;根据下列流程图编写程序实现相应处理&#xff0c;执行j10*x-y返回文字“j1&#xff1a;”和计算值&#xff0c;执行j(x-y)*(10⁵%7)返回文字“j2&#xff1a;”和计算值&#xff0c;执行jy*log(x10)返回文字“j3&#xff1a;”和计算值…

通义千问AI挑战赛赛后反思

个人理解&#xff1a; 初赛阶段主要聚焦在如何通过 SFT 提升基础模型的代码能力&#xff0c;需要选手基于最新开源的 Qwen 1.8 模型作为基础模型&#xff0c;上分的关键主要通过收集高质量的代码数据提升模型的在Python, JavaScript, Java, Go, C, Rust六种编程语言的代码生成…

若依框架实现排序【升序或降序】很简单

前端实现 1. 在表格上加监听函数sort-change。如下红框所示&#xff1a; 2. 在表行上加排序字:sort-orders&#xff0c;可排序字sortable。如下红框所示&#xff1a; 3. 添加监听函数实现。代码如下&#xff1a; handleSortChange(column) {this.queryParams.orderByColumn …

使用emu8086实现——循环结构程序设计

一、实验目的 1.掌握循环结构程序设计的方法&#xff1b; 2.掌握数据块传送程序设计的方法&#xff1b; 3.掌握串传送指令的应用。 二、实验内容 1、计算S12*33*4...N*(N1)&#xff0c;直到N*(N1)项大于200为止。编写程序&#xff0c;计算上式的结果。 代码及注释&#…

考研经验总结——目录

文章目录 一、写作顺序二、个人情况说明三、读评论四、一些小牢骚五、一些注意事项&#xff08;持续更新&#xff09; 一、写作顺序 我将准备从三个阶段开始介绍吧 考研前考研中考研后&#xff08;也就是现在我的这种情况&#xff09; 考研前我会分为&#xff1a;数学、专业…

国图公考:2024山东省事业单位发布招聘公告

更多信息可以登录山东人事考试信息查看&#xff01;

webpack执行流程知识点总结

webpack的运行流程 Webpack 的运行流程是一个串行的过程&#xff0c;从启动到结束会依次执行以下流程&#xff1a; 在以上过程中&#xff0c;Webpack 会在特定的时间点广播出特定的事件&#xff0c;插件在监听到感兴趣的事件后会执行特定的逻辑&#xff0c;并且插件可以调用 We…

艾瑞报告:HR数字化需关注体系化能力,红海云等标杆厂商引领一体化趋势

新全球化时代背景下&#xff0c;企业经营所面临的国内外环境的不确定性增强&#xff0c;如何从不确定性中找到确定性成了大多数企业的关注要点。近日&#xff0c;艾瑞咨询发布《2023中国人力资源数字化研究报告》&#xff0c;从数字化转型的角度切入&#xff0c;探讨数字化如何…

原型设计工具Axure RP结合内网穿透实现本地web页面公网访问协同办公

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

进阶Docker3:Dokerfile构建镜像

目录 Dockerfile 构建基础镜像 基本机构 命令&#xff1a; 命令解释&#xff1a; 准备工作 创建镜像 上传镜像 Dockerfile Dockerfile 是一个文本格式的配置文件&#xff0c; 用户可以使用 Dockerfile 来快速创建自定义的镜像&#xff0c;另外&#xff0c;使 用Docke…

neo4j图数据库的简单操作记录

知识图谱文件导出 首先停止运行sudo neo4j stop然后导出数据库 导出格式为&#xff1a; 具体命令如下sudo neo4j-admin database dump --to-path/home/ neo4j最后重启sudo neo4j start知识图谱外观修改 在网页点击节点&#xff0c;选中一个表情后点击&#xff0c;可修改其颜…

Beauty algorithm(七)瘦脸

瘦脸的实现采用局部平移法。 一、skills 前瞻 局部平移 二、目标区域定位 左脸: 关键点选择3、5点,基点30 rmax:计算两点5-3间的距离, |x-c|:图像任一点到固定基点c的距离 |m-c|:两固定点距离 右脸: 关键点选择