代码随想录算法训练营第22天(py)| 二叉树 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

本文主要是介绍代码随想录算法训练营第22天(py)| 二叉树 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

669. 修剪二叉搜索树

力扣链接
给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L)

思路

如果当前节点元素小于low,递归右子树,返回符合条件的头节点
如果当前节点元素大于high,递归左子树,返回复合条件的头节点
最后root.left接入符合条件的左孩子,root.right接入符合条件的右孩子

class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if root == None:return rootif root.val < low:right = self.trimBST(root.right, low, high)return rightif root.val > high:left = self.trimBST(root.left, low, high)return leftroot.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root

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

力扣链接
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 平衡二叉搜索树(左右子树深度差不超过1)

思路

对于有序数组,中间元素为根节点,右边的元素放右孩子,左边的元素放左孩子。

class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:root = self.traversal(nums, 0, len(nums)-1)return rootdef traversal(self, nums, left, right):if left > right:return Nonemid = (left + right)//2root = TreeNode(nums[mid])root.left = self.traversal(nums, left, mid-1)root.right = self.traversal(nums, mid+1, right)return root

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

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

思路

保存上一节点的数值,用中序遍历(反着的)构建

class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.pre = 0 # 记录前一个节点的值self.traversal(root)return rootdef traversal(self, node):if node is None:return # 中序遍历(倒序)# 右self.traversal(node.right)# 中node.val += self.preself.pre = node.val# 左self.traversal(node.left)

这篇关于代码随想录算法训练营第22天(py)| 二叉树 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1015013

相关文章

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

一文教你Python引入其他文件夹下的.py文件

《一文教你Python引入其他文件夹下的.py文件》这篇文章主要为大家详细介绍了如何在Python中引入其他文件夹里的.py文件,并探讨几种常见的实现方式,有需要的小伙伴可以根据需求进行选择... 目录1. 使用sys.path动态添加路径2. 使用相对导入(适用于包结构)3. 使用pythonPATH环境

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时