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

算法训练营第二十三天(二叉树完结)

算法训练营第二十三天(二叉树完结)

669. 修剪二叉搜索树

力扣题目链接(opens new window)

题目

给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

在这里插入图片描述

在这里插入图片描述

解答

自己写的递归
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null)return null;if (root.val == low){root.left = null;root.right = trimBST(root.right,low,high);}else if (root.val == high){root.right = null;root.left = trimBST(root.left,low,high);}else if (root.val > low && root.val < high){root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);}else if (root.val < low)root = trimBST(root.right,low,high);elseroot = trimBST(root.left,low,high);return root;}
}
简化递归
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null)return null;if (root.val < low)root = trimBST(root.right,low,high);//左子树和根都不要了else if (root.val > high)root = trimBST(root.left,low,high);//右子树和根都不要了else {// root在[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 low, int high) {if(root == null)return null;// 处理头结点,让root移动到[L, R] 范围内,注意是左闭右闭while(root != null && (root.val < low || root.val > high)){if(root.val < low)root = root.right;// 小于L往右走elseroot = root.left;// 大于R往左走}TreeNode curr = root;// 此时root已经在[L, R] 范围内,处理左孩子元素小于L的情况while(curr != null){while(curr.left != null && curr.left.val < low){curr.left = curr.left.right;}curr = curr.left;}//go back to root;curr = root;// 此时root已经在[L, R] 范围内,处理右孩子大于R的情况while(curr != null){while(curr.right != null && curr.right.val > high){curr.right = curr.right.left;}curr = curr.right;}return root;}
}

在这里插入图片描述

108.将有序数组转换为二叉搜索树

力扣题目链接(opens new window)

题目

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

在这里插入图片描述

解答

使用新的空间
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if (nums.length == 0)return null;int midIndex = nums.length / 2;TreeNode root = new TreeNode(nums[midIndex]);root.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,midIndex));root.right = sortedArrayToBST(Arrays.copyOfRange(nums,midIndex + 1,nums.length));return root;}
}
使用索引(左闭右开)
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length);}//左闭右开public TreeNode sortedArrayToBST(int[] nums, int left, int right) {if (left >= right) {return null;}if (right - left == 1) {return new TreeNode(nums[left]);}int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = sortedArrayToBST(nums, left, mid);root.right = sortedArrayToBST(nums, mid + 1, right);return root;}
}

538.把二叉搜索树转换为累加树

力扣题目链接(opens new window)

题目

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(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 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树

解答

  • 采取中序遍历,不过是右中左,相当于从最大到最小遍历
  • 对于每一个结点,他的值都等于他之前遍历的所有的值的和
  • 下面的sum其实也相当于双指针中的pre,初始状态pre指向空,cur指向最右侧结点
递归
class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {travel(root);return root;}private void travel(TreeNode root){if (root == null)return;//右中左travel(root.right);root.val += sum;sum = root.val;travel(root.left);}
}
//不好理解
class Solution {public TreeNode convertBST(TreeNode root) {travel(root,0);return root;}private int travel(TreeNode root,int sum){if (root == null)return sum;//右中左root.val += travel(root.right,sum);return travel(root.left,root.val);//每次执行完都是为下一轮做准备}
}
迭代
class Solution {public TreeNode convertBST(TreeNode root) {//右中左Stack<TreeNode> stack = new Stack<>();int sum = 0;TreeNode cur = root;//右中左while (!stack.isEmpty() || cur != null){while (cur != null){stack.push(cur);cur = cur.right;}cur = stack.pop();cur.val += sum;sum = cur.val;cur = cur.left;}return root;}
}

相关文章:

算法训练营第二十三天(二叉树完结)

算法训练营第二十三天&#xff08;二叉树完结&#xff09; 669. 修剪二叉搜索树 力扣题目链接(opens new window) 题目 给定一个二叉搜索树&#xff0c;同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树&#xff0c;使得所有节点的值在[L, R]中 (R>L) 。你可能需要改…...

mysql主从复制Slave_SQL_Running: No

1、SHOW SLAVE STATUS \G; Slave_SQL_Running: No 解决方案&#xff1a; 重新同步主库和从库的数据 1、从库先停掉slave stop slave; 2、在主库查看此时的日志文件和位置 show master status; 3、在从库中执行 change master to master_host192.168.2.177,master_userslave…...

【SpringBoot】SpringBoot项目快速搭建

本文将介绍Springboot项目的快速搭建 快速创建SpringBoot项目 打开IDEA在File->New->Project中新建项目 点击左侧的Spring Initializr 输入以下信息&#xff1a; Name 项目名称Group 根据公司域名来&#xff0c;或者默认com.example【倒序域名】Package Name 包名&am…...

Terraform 状态不同步处理

背景 在使用 Terraform 创建 TencentCloud TKE 的时候&#xff0c;手贱把 node pool 删掉了。导致执行 destroy, plan 都会报错。 │ Error: [TencentCloudSDKError] CodeInternalError.UnexpectedInternal, Messagerelated node pool query err(get node pool failed: [E501…...

4.2.k8s的pod-标签管理、镜像拉取策略、容器重启策略、资源限制、优雅终止

一、标签管理 1.标签在k8s中极其重要&#xff0c;大多数资源的相互关联就需要使用标签&#xff1b;也就是说&#xff0c;资源的相互关联大多数时候&#xff0c;是使用标签进行关联的&#xff1b; 2.其他作用&#xff0c;在k8s集群中&#xff0c;node节点的一些操作比如污点及污…...

能源党建后台项目总结

1.引入 本次框架是Ruoyi-plusvue2element组合。 2.样式 由于是后台项目&#xff0c;样式要求统一&#xff0c;不可以有的输入框长有的短。着重几点&#xff1a; 1.关于form表单应该如何水平布局 在element中&#xff0c;form有个属性叫&#xff1a;:inline"true"…...

股票高胜率的交易法则是什么?

股票交易中的高胜率交易法则并非一成不变&#xff0c;而是根据市场状况、个人投资风格和经验等多种因素综合而定的。以下是一些有助于提升交易胜率的法则和策略&#xff1a; 1.趋势跟踪法则&#xff1a;在股票交易中&#xff0c;趋势跟踪是一种有效的策略。通过观察大盘和个股…...

C语言 | sizeof与strlen的区别(附笔试题)

目录&#xff1a; 1. sizeof和strlen的对比 2. 数组和指针 笔试题解析 3. 指针运算 笔试题解析 内容多多&#xff0c;需耐心看完&#xff0c;加油&#xff01;&#xff01;&#xff01; 一.sizeof和strlen的对比 1.1 sizeof 在学习操作符的时候&#xff0c;我们学习了 s…...

AI自动绘画器介绍和应用场景

AI自动绘画器是一种利用人工智能技术来生成绘画作品的工具。以下是一些常见的AI自动绘画器&#xff1a; DeepDream&#xff1a; 风格&#xff1a;可以生成三种风格的图片&#xff0c;包括深度梦幻风格、深度风格和浅层风格。应用场景&#xff1a;起初设计用于帮助研究人员理解…...

java二叉树前中后序遍历

代码随想录解题思路&#x1f192;力扣前序题目&#x1f192;力扣中序题目&#x1f192;力扣后序题目 递归遍历 // 前序遍历 class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res new ArrayList<>();preorder(root…...

【LeetCode刷题笔记】LeetCode 1365.有多少小于当前数字的数字

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞 关注支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; 更多算法知识专栏&#xff1a;算法分析&#x1f525; 给大家跳段街舞感谢…...

室内定位中文综述阅读

1 室内高精度定位技术总结与展望 [4]柳景斌,赵智博,胡宁松等.室内高精度定位技术总结与展望[J].武汉大学学报(信息科学 版),2022,47(07):997-1008.DOI:10.13203/j.whugis20220029. 1.1.1 WiFi‐RTT定位 2016 年 12 月&#xff0c;随着新版 IEEE802.11 标准的公布&#xff0c…...

微信小程序uniapp+vue电力巡线任务故障报修管理系统2q91t

uni-app框架&#xff1a;使用Vue.js开发跨平台应用的前端框架&#xff0c;编写一套代码&#xff0c;可编译到Android、小程序等平台。 前端开发:vue 语言&#xff1a;javapythonnodejsphp均支持 运行软件:idea/eclipse/vscode/pycharm/wamp均支持 框架支持:Ssm/django/flask/t…...

springboot国际化多语言

1,新建国际化多语言文件 在resources目录下新建 messages.properties 其他语言的文件 编辑messages.properties文件,下方从text切换到Resource Bundle ,即可对照着编辑多语言文件 (如果没有找到Resource Bundle,先在settings->plugins中安装Resource Bundle Editor) 2,配…...

set和map

这里是目录标题 setinsertfinderasecountlower_boundupper_boundmultisetset的应用 mappairinsertinsert的pair map的遍历map对[ ]的重载(重点)multimap set set的普通迭代器和const迭代器都不支持修改。(这点可以根据源代码看出来&#xff0c;都是对const iterator进行了type…...

Open CASCADE学习|求曲面的参数空间

在三维空间中&#xff0c;任意的曲面都可以通过特定的方法映射到一个二维参数平面上&#xff0c;从而对其进行详细的几何分析和处理。首先&#xff0c;我们需要从三维模型中提取出特定的曲面&#xff0c;这通常被称为“Face”。一个face可以被视为三维空间中的一个封闭区域&…...

代码随想录阅读笔记-二叉树【总结】

二叉树的理论基础 代码随想录 (programmercarl.com)&#xff1a;二叉树的种类、存储方式、遍历方式、定义方式 二叉树的遍历方式 深度优先遍历 代码随想录阅读笔记-二叉树【递归遍历】-CSDN博客&#xff1a;递归三部曲初次亮相代码随想录阅读笔记-二叉树【迭代遍历】-CSDN博…...

【SpringBoot整合系列】SpringBoot整合FastDFS(二)

目录 SpringBoot整合FastDFSJava客户端/依赖常用api接口解释1.uploadFile参数返回值 2.uploadSlaveFile参数返回值 3.getMetadata参数返回值 4.overwriteMetadata参数&#xff1a;返回值&#xff1a;无 5.mergeMetadata参数&#xff1a;返回值&#xff1a;无 6.queryFileInfo参…...

L2-2 巴音布鲁克永远的土(二分+并查集)

思路&#xff1a;我们可以二分答案&#xff0c;然后判断当前答案合不合理。 对于判断答案合理&#xff0c;可以用并查集&#xff0c;看mid能否把所有检查点连进一个集合中&#xff0c;枚举每个结点&#xff0c;如何当前结点周围的四个方向可以连的话&#xff0c;就加进同一个集…...

Spring Cloud学习笔记:Eureka简介,Eureka简单样例

这是本人学习的总结&#xff0c;主要学习资料如下 - 马士兵教育 [TOC](目录)1、Eureka 1.1、架构 Eureka是SpringCloud Nexflix的核心子模块&#xff0c;其中包含Server和Client。 Server提供服务注册&#xff0c;存储所有可用服务节点。 Client用于简化和Server的通讯复杂…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

智能体革命:企业如何构建自主决策的AI代理?

OpenAI智能代理构建实用指南详解 随着大型语言模型&#xff08;LLM&#xff09;在推理、多模态理解和工具调用能力上的进步&#xff0c;智能代理&#xff08;Agents&#xff09;成为自动化领域的新突破。与传统软件仅帮助用户自动化流程不同&#xff0c;智能代理能够自主执行工…...