669. 修剪二叉搜索树 ,108.将有序数组转换为二叉搜索树 , 538.把二叉搜索树转换为累加树

简介: 1. **修剪二叉搜索树(669号题)**:通过递归方法,移除值不在指定范围 `[low, high]` 内的节点,同时保持树中剩余节点的相对结构不变。核心思想是根据当前节点值与边界的关系决定保留左子树还是右子树。2. **将有序数组转换为二叉搜索树(108号题)**:将一个升序排列的数组转化为一棵高度平衡的二叉搜索树。采用分治法,选取数组中间元素作为根节点,递归构建左右子树。即使数组长度为偶数,选择任一中间值均可满足条件。3. **把二叉搜索树转换为累加树(538号题)**:通过修改二叉搜索树中每个节点的值,使其等于原树中所有大于或等于该节点值的和。

题目:

  1. 修剪二叉搜索树
    给你二叉搜索树的根节点 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
题解:
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;
}
};

题目:

  1. 将有序数组转换为二叉搜索树
    给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列
思考历程与知识点:
本质就是寻找分割点,分割点作为当前节点,然后递归左区间和右区间。

分割点就是数组中间位置的节点。

那么为问题来了,如果数组长度为偶数,中间节点有两个,取哪一个?

取哪一个都可以,只不过构成了不同的平衡二叉搜索树。

题解:
class Solution {
private:
TreeNode traversal(vector& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode
root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode sortedArrayToBST(vector& nums) {
TreeNode
root = traversal(nums, 0, nums.size() - 1);
return root;
}
};

题目:

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

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

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意:本题和 1038: 力扣 相同

示例 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 {
private:
int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode cur) { // 右中左遍历
if (cur == NULL) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
public:
TreeNode
convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};

————————————————

相关文章
|
安全 API 数据安全/隐私保护
smtp用户名,验证身份的名称是什么?
SMTP用户名是验证身份的标识,用于证明有权使用SMTP服务器发送邮件。它通常与邮箱地址关联,如`example@example.com`。配合smtp密码,二者组成身份验证的钥匙。安全使用这些信息至关重要,避免在不安全环境中输入,以保障邮件发送的安全和顺利。AokSend提供安全的发信服务,支持smtp/api接口,确保高触达发信。
|
传感器 机器学习/深度学习 编解码
图像配准:基于 OpenCV 的高效实现
在这篇文章中,我将对图像配准进行一个简单概述,展示一个最小的 OpenCV 实现,并展示一个可以使配准过程更加高效的简单技巧。
|
4月前
|
弹性计算 监控 网络协议
阿里云国际版:ECS下载速度慢排查方法
很多运维团队在阿里云ECS上遇到过一个“反直觉”的故障:监控面板显示带宽利用率只有两三成,甚至远未触及实例规格上限,但实际下载一个大文件却慢得让人抓狂——用scp拷贝居然只有几百KB/s,而ping延迟一切正常。这类问题的根因往往不在机器性能,而在传输控制、链路损耗这些容易被忽略的底层环节。下面从带宽与下载速度的真实关系、TCP拥塞控制的影响以及网络链路损耗三个维度展开,把常见的诊断路径讲清楚。
455 0
阿里云国际版:ECS下载速度慢排查方法
|
3月前
|
数据采集 人工智能 搜索推荐
AI 搜索时代的 Q4 备战手册:GEO 优化的底层逻辑与落地三步法
随着 ChatGPT、Google AI Overview 等生成式 AI 成为消费者购物决策的新入口,品牌能否出现在 AI 的推荐列表中,将直接影响 Q4 黑五的流量与转化。 本文从技术层面拆解了 GEO(生成式引擎优化)的核心逻辑:大模型存在 30–60 天的实体索引滞后期,这意味着 10 月才开始优化已为时过晚。
|
4月前
|
人工智能 自然语言处理 API
Token Plan怎么用?API Key 和 Base URL获取方法,支持接入OpenClaw、Claude、Cursor及Codex等AI工具
阿里云百炼Token Plan团队版是面向企业与开发者的AI大模型订阅服务,以Credits统一计量,支持Qwen、GLM、Kimi等150+文本/图像模型,兼容OpenClaw、Cursor等主流AI工具,提供团队管理、数据安全与高峰不排队保障。在阿里云百炼官网:https://t.aliyun.com/U/fPVHqY 免费领取千万Tokens
|
监控 供应链 安全
SentinelOne零信任架构(ZTA)介绍
随着网络威胁日益复杂,传统安全模式面临挑战。零信任架构(ZTA)以“永不信任,始终验证”为核心,通过持续验证、最小权限、微分段等原则,提升企业数据安全,尤其适应远程办公与云环境。本文详解其核心原则、优势、实施难点及行业应用,助力企业构建更强安全防线。
1489 1
|
人工智能 自然语言处理 算法
网信办整治 AI 技术滥用,AI 企业如何合规运营
中央网信办开展为期3个月的“清朗・整治AI技术滥用”专项行动,旨在规范AI服务与应用,保障公民权益,促进行业健康发展。文章从算法备案、数据合规管理、内容审核、标识要求、重点领域风险防控、防止侵权、杜绝网络水军及保护未成年人权益八个方面,详细解析了AI企业在运营中需遵循的具体要求与措施,强调企业应主动落实合规,推动AI行业健康有序发展。
|
安全 Ubuntu 网络安全
本地服务器 Odoo 安装指南,并实现公网访问
本指南详细介绍基于 Odoo 的企业应用部署流程。首先通过 VMware 安装虚拟机并配置 Ubuntu 系统,为运行环境打下基础;接着利用 Websoft9 平台简化中间件与 Odoo 服务的安装,实现快速部署与版本管理;然后借助 cpolar 实现内网穿透并完成域名解析,确保公网访问畅通;最后进行功能测试与性能优化,提供运维建议以保障系统稳定性和安全性。适合初学者及中小型企业参考实施。
1501 4
|
11月前
|
存储 人工智能 JSON
🤖 Agent系统
大模型Agent是具备自主规划、推理、工具调用与记忆能力的智能系统,通过“大脑-感知-行动-记忆”架构实现复杂任务分解与持续交互。支持函数调用与多工具集成,广泛应用于搜索、计算、天气等场景。主流框架如LangChain、AutoGPT、CrewAI等各具特色,适用于原型开发、多Agent协作与企业级应用,是AI进化的关键方向。
|
存储 监控 Java
Java多线程优化:提高线程池性能的技巧与实践
Java多线程优化:提高线程池性能的技巧与实践
809 1