Day26 669修剪二叉搜索树 108有序数组转为二叉搜索树 538二叉搜索树转换为累加树
669 修剪二叉搜索树
给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return root; //如果是空节点直接返回//如果结点小于最小结点,这个肯定要删,此时看一下右孩子们小不小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;}
};
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;}
};
108.将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
class Solution {
private:TreeNode* traversal(vector<int>& nums, int left, int right) {if(right < left) return nullptr;//为了保证平衡,新创建的一定是中间头结点int middle = (left+right)/2;TreeNode* root = new TreeNode(nums[middle]);root->left = traversal(nums,left,middle-1);root->right = traversal(nums, middle+1,right);return root;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return traversal(nums,0,nums.size()-1);}
};
迭代法比较复杂,这里先记录一下
class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {if (nums.size() == 0) return nullptr;TreeNode* root = new TreeNode(0); // 初始根节点queue<TreeNode*> nodeQue; // 放遍历的节点queue<int> leftQue; // 保存左区间下标queue<int> rightQue; // 保存右区间下标nodeQue.push(root); // 根节点入队列leftQue.push(0); // 0为左区间下标初始位置rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下标初始位置while (!nodeQue.empty()) {TreeNode* curNode = nodeQue.front();nodeQue.pop();int left = leftQue.front(); leftQue.pop();int right = rightQue.front(); rightQue.pop();int mid = left + ((right - left) / 2);curNode->val = nums[mid]; // 将mid对应的元素给中间节点if (left <= mid - 1) { // 处理左区间curNode->left = new TreeNode(0);nodeQue.push(curNode->left);leftQue.push(left);rightQue.push(mid - 1);}if (right >= mid + 1) { // 处理右区间curNode->right = new TreeNode(0);nodeQue.push(curNode->right);leftQue.push(mid + 1);rightQue.push(right);}}return root;}
};
538 二叉搜索树转换为累加树
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;}
};
class Solution {
private:int pre; // 记录前一个节点的数值void traversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->right; // 右} else {cur = st.top(); // 中st.pop();cur->val += pre;pre = cur->val;cur = cur->left; // 左}}}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};
二叉树,就此完结!
相关文章:
Day26 669修剪二叉搜索树 108有序数组转为二叉搜索树 538二叉搜索树转换为累加树
669 修剪二叉搜索树 给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。 class Solution { pub…...

优化CentOS 7.6的HTTP隧道代理网络性能
在CentOS 7.6上,通过HTTP隧道代理优化网络性能是一项复杂且细致的任务。首先,我们要了解HTTP隧道代理的工作原理:通过建立一个安全的隧道,HTTP隧道代理允许用户绕过某些网络限制,提高数据传输的速度和安全性。然而&…...
第二篇ts,es6箭头函数结合typescript,和for...of
1.基本用法: const f v > v// 等同于const f function(v) {return v}2.箭头函数返回数组 const f () > {const list [1,2,3]// 直接返回一个对象return list.map(it > ({id: it}))}const result f() // [{id:1},{id:2},{id:3}]3.箭头函数和变量解构结合使用 cons…...
异构多品牌高清视频监控接入-技术方案
目 录 一、概述 二、建设目标及需求 (一)建设总目标 (二)需求分析 三、设计依据与设计原则 (一)设计依据 (二)设计原则 1、先进性与适用性 2、经济性与实用性 3、可靠性与安全性 4、开放性 5、可扩充性 6、追求最优化的系统设备配置 7、提高监管…...
编程探秘:Python深渊之旅-----机器学习入门(七)
团队决定在他们的项目中加入一些机器学习功能。瑞宝,对新技术充满好奇,跃跃欲试地想了解更多。 瑞宝(兴奋地):我一直想学习机器学习,现在终于有机会了! 龙(微笑着)&…...

SpringMVC 学习博客记录
文章目录 Servlet请求转发和请求包含RequestDispatcher HandlerInterceptor组件实际运用场景 HandlerMapping&RequestMappingInfo(HandlerMapping)HandlerExecutionChainHandlerAdapter源码学习知识点博客记录 Servlet请求转发和请求包含 RequestDispatcher Request#getR…...

重磅!OpenAI正式发布,自定义ChatGPT商店!
1月11日凌晨,OpenAI在官网正式发布了,自定义GPT商店,可以帮助用户找到目前最好用、流行的自定义ChatGPT助手。 在2024年第一季度,OpenAI将启动GPT 开发者收入计划。首先,美国地区的开发者将根据用户对其 GPT 的使用情…...

LeetCode讲解篇之47. 全排列 II
文章目录 题目描述题解思路题解代码 题目描述 题解思路 初始化一个nums中元素是否被访问的数组used、记录还需要递归的深度deep 遍历nums 如果当前元素被访问过或者当前元素等于前一个元素且前一个元素没被访问过就跳过该次遍历 否则选择当前元素,继续递归 直到…...

机器学习~从入门到精通(二)线性回归算法和多元线性回归
为什么要做数据归一化 一、数据归一化: 1.最值归一化 2.均值方差归一化import numpy as npX np.random.randint(1,100,size100) X X.reshape(-1,2) X.shape X np.array(X,dtypefloat) X[:,0] (X[:,0]-np.min(X[:,0]))/(np.max(X[:,0])-np.min(X[:,0])) X[:,1]…...
IPv6组播--PIM
IPv6组播路由协议 PIM(IPv6)作为一种IPv6网络中的组播路由协议,主要用于将网络中的组播数据流引入到有组播数据请求的组成员所连接的路由器上,从而实现组播数据流的路由查找与转发。 PIM(IPv6)协议包括PIM-SM(IPv6)和PIM-DM(IPv5)两种模式 IPv6组播协议定义 PIM(…...

如何在Spring Boot中使用EhCache缓存
1、EhCache介绍 在查询数据的时候,数据大多来自于数据库,我们会基于SQL语句与数据库交互,数据库一般会基于本地磁盘IO将数据读取到内存,返回给Java服务端,我们再将数据响应给前端,做数据展示。 但是MySQL…...

PDF 文档解除密码
PDF 文档解除密码 1. 文件 -> 文档属性 -> 安全 -> 文档限制摘要2. PDF365References 1. 文件 -> 文档属性 -> 安全 -> 文档限制摘要 密码保护《算法设计与分析基础_第3版.pdf》 2. PDF365 https://www.pdf365.cn/ 免费功能 -> PDF 去密码 开始去除 Re…...
React16源码: React中的expirationTime过期时间的计算源码实现
expirationTime 的计算方式 先看expirationTime相关的源代码,这里是异步的计算方式,它会有一个过期时间异步任务优先级比较低,可以被打断,防止一直被打断导致不能执行,所以React给它设置了 expirationTime 过期时间也…...
程序设计语言的分类
编译与解释 编译型 将源代码转换成目标代码,通常源代码是高级语言代码,目标代码是机器语言代码,执行编译的计算机程序称为编译器。 eg:java 好处:对于相同的源代码编译产生的目标代码执行速度更快,目标代码不需要编译…...

Python轻松实现炫酷的手势检测
大家好,今天分享一个非常有意思且十分简单的python库——mediapipe库。该库集成了大量的深度学习模型,短短几行代码,就可以快速实现一个炫酷的实例,本文就以手势检测为例,展示一下这个强大的开源库。 mediapipe由Goog…...

什么是信噪比
大家好,今天给大家介绍什么是信噪比,文章末尾附有分享大家一个资料包,差不多150多G。里面学习内容、面经、项目都比较新也比较全!可进群免费领取。 “信噪比”是电子技术中经常用到的一个词组,知道它的确切含义有一定意…...

学习redis有效期和数据类型
1、安装redis和连接redis 参考:ubuntu安装单个redis服务_ubuntu redis单机版安装-CSDN博客 连接redis:redis-cli.exe -h localhost -p 6379 -a 123456 2、Redis数据类型 以下操作我们在图形化界面演示。 2.1、五种常用数据类型介绍 Redis存储的是key…...

【linux】进程管理
前言 linux也有类似于windows的任务管理器的功能,我们也可以通过这个功能查看当前的进程情况。 语法 ps [-e] [-f] -e显示所有进程 -f显示完整的信息 我们可以直接用-ef来简化指令。 案例演示 信息过滤 但是如果我们直接这么输入的话,可以看到他回复…...
k8s operator从0到1实践
文章目录 环境准备一个k8s集群开发工具包mac安装 实践初始化operator项目核心逻辑编写测试验证验证 部署 参考 环境准备 一个k8s集群 推荐使用docker-desktop,本地单机集群 开发工具包 这里推荐使用脚手架工具kubebuilder 使用脚手架工具,能生成项目…...

【动态规划】dp多状态问题
欢迎来到Cefler的博客😁 🕌博客主页:那个传说中的man的主页 🏠个人专栏:题目解析 🌎推荐文章:【LeetCode】winter vacation training 目录 👉🏻按摩师👉&…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...