代码随想录算法训练营 day23| ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

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

文章目录

  • 前言
  • 669. 修剪二叉搜索树
    • 思路
    • 方法一 递归法
    • 方法二 迭代法
  • 108.将有序数组转换为二叉搜索树
    • 思路
    • 方法一 递归法
    • 方法二 迭代法
  • 538.把二叉搜索树转换为累加树
    • 思路
    • 方法一
    • 方法二
  • 总结


前言

迭代法都没看主要是669和538【538很简单】

669. 修剪二叉搜索树

在这里插入图片描述
在这里插入图片描述

思路

不用看教程,思路很清晰
💖总体思路【单层递归逻辑】

  1. 如果当前节点的值小于low,就处理root的右子树(因为左子树一定不符合),返回右子树的修剪结果,也就是return traversal(root.right)
  2. 如果root的val大于high的话,就处理root的左子树(因为右子树一定不符合了),返回左子树修剪之后的结果,也就是return traversal(root.left)
  3. 如果root的val处于区间之间,需要修剪他的左右子树,也就是root.left = traversal(root.left),右边子树同理。
    终止条件:如果为null,返回null

方法一 递归法

class Solution(object):def trimBST(self, root, low, high):""":type root: TreeNode:type low: int:type high: int:rtype: TreeNode"""if root == None: return Noneif root.val < low: return self.trimBST(root.right,low,high)if root.val > high:return self.trimBST(root.left,low,high)if root.val<= high and root.val>=low:root.left = self.trimBST(root.left,low,high)root.right = self.trimBST(root.right,low,high)return root

方法二 迭代法

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

在这里插入图片描述
本题掌握递归法就够了,递归法比较复杂,升级版本;

思路

递归三部曲

  1. 传入返回值:传入的是指向数组的指针,和范围;函数返回的是由这个范围内的数组构成的二叉树的根节点
  2. 终止条件:如果传入的数组范围中left>right,那就返回none
  3. 单层递归逻辑:找到中间节点,作为root,root-left为左边区间构建的二叉树,右边同理

注意点

  1. . 为了保证构造的是平衡二叉树,所以根节点是中间的值
  2. . 注意传入的数组范围区间:本题中定义的是左闭右闭

方法一 递归法

写代码注意点:

  1. 因为是左闭右闭的,所以判断迭代终止条件为left大于right
  2. 传入的只是数组,而不是节点,这个要注意
class Solution(object):def traversal(self,left,right):if left > right: return None mid = (left + right)//2node = TreeNode(val = self.nums[mid])node.left = self.traversal(left,mid-1)node.right = self.traversal(mid+1,right)return nodedef sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: TreeNode"""self.nums = numsroot = self.traversal(0,len(nums)-1)return root# 精简版 传递切片class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:if not nums:returnmid = len(nums) // 2root = TreeNode(nums[mid])root.left = self.sortedArrayToBST(nums[:mid])root.right = self.sortedArrayToBST(nums[mid + 1 :])return root       

方法二 迭代法

本题迭代法比较困难,就不用放了。

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

在这里插入图片描述
题目的意思是:将二叉树中某节点的新的值为原先树中大于这个节点的数的值的累加。

思路

总体思路:很简单,右中左遍历就行。定义一个全局变量累加

方法一

class Solution(object):def __init__(self):self.count = 0def traversal(self,root):if root == None: return Noneif root.right: self.traversal(root.right)self.count += root.valroot.val = self.countif root.left: self.traversal(root.left)return rootdef convertBST(self, root):""":type root: TreeNode:rtype: TreeNode"""re = self.traversal(root)return re

方法二



总结

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


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

相关文章

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

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

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

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换