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

代码随想录 - Day30 - 修剪二叉树,转换二叉树 + 二叉树总结

代码随想录 - Day30 - 修剪二叉树,转换二叉树 + 二叉树总结

669. 修剪二叉搜索树

有点像是删除二叉搜索树的变形,改变了删除条件而已。
递归法:

class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return rootif root.val < low:      # 当前节点小于low,不用再看其左子树,遍历其右子树即可right = self.trimBST(root.right, low, high)return rightif root.val > high:     # 当前节点大于high,不用再看其右子树,遍历其左子树即可left = self.trimBST(root.left, low, high)return leftroot.left = self.trimBST(root.left, low, high)      # root.left接入符合条件的左孩子root.right = self.trimBST(root.right, low, high)    # root.right接入符合条件的右孩子return root

迭代法:

'''
在剪枝的时候,可以分为三步:
将root移动到[L, R] 范围内,注意是左闭右闭区间
剪枝左子树
剪枝右子树
'''
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return root# 处理头节点,把头结点放到[low, high]范围内while root and (root.val < low or root.val > high):if root.val < low:      # 小于low往右走root = root.rightelse:                   # 大于high往左走root = root.leftcurleft, curright = root, root# 处理左孩子元素小于low的情况while curleft:while curleft.left and curleft.left.val < low:curleft.left = curleft.left.rightcurleft = curleft.left# 处理右孩子元素大于high的情况while curright:while curright.right and curright.right.val > high:curright.right = curright.right.leftcurright = curright.rightreturn root

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

对于奇数长度的数组可以直接取中点,对于偶数长度的数组则需要用mid = int(left + ((right - left) / 2))
中点作为根节点,左右两侧则分别为左子树和右子树,依次进行递归遍历。

class Solution:# 左闭右闭区间[left, right]def traversal(self, nums, left, right):if left > right:return Nonemid = int(left + ((right - left) / 2))      # 防止越界root = TreeNode(nums[mid])root.left = self.traversal(nums, left, mid - 1)root.right = self.traversal(nums, mid + 1, right)return rootdef sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:root = self.traversal(nums, 0, len(nums) - 1)return root

迭代法:用队列模拟递归过程

from collections import dequeclass Solution:def sortedArrayToBST(self, nums: List[int]) -> TreeNode:if len(nums) == 0:return Noneroot = TreeNode(0)  # 初始根节点nodeQue = deque()   # 放遍历的节点leftQue = deque()   # 保存左区间下标rightQue = deque()  # 保存右区间下标nodeQue.append(root)               # 根节点入队列leftQue.append(0)                  # 0为左区间下标初始位置rightQue.append(len(nums) - 1)     # len(nums) - 1为右区间下标初始位置while nodeQue:curNode = nodeQue.popleft()left = leftQue.popleft()right = rightQue.popleft()mid = left + (right - left) // 2curNode.val = nums[mid]     # 将mid对应的元素给中间节点if left <= mid - 1:         # 处理左区间curNode.left = TreeNode(0)nodeQue.append(curNode.left)leftQue.append(left)rightQue.append(mid - 1)if right >= mid + 1:        # 处理右区间curNode.right = TreeNode(0)nodeQue.append(curNode.right)leftQue.append(mid + 1)rightQue.append(right)return root

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

题目中的累加是右中左的顺序进行累加,从最大的节点值累加到最小的节点值。
所以要反中序遍历该二叉树,然后顺序累加。
需要一个pre指针记录当前节点的前一个节点,这样才能方便累加。

class Solution:def traversal(self, cur):       # 右中左遍历if not cur:                 # 终止条件returnself.traversal(cur.right)   # 右cur.val += self.pre         # 中self.pre = cur.valself.traversal(cur.left)    # 左def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.pre = 0                # 记录前一个节点的数值self.traversal(root)return root

或者写成这样也可以:

class Solution:def __init__(self):               # 记录前一个节点的数值self.pre = 0def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:                  # 终止条件returnself.convertBST(root.right)   # 右root.val += self.pre          # 中self.pre = root.valself.convertBST(root.left)    # 左return root

迭代法:

class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: return rootstack = []result = []cur = rootpre = 0         # 记录前一个节点的数值while cur or stack:if cur:                 # 右stack.append(cur)cur = cur.rightelse: cur = stack.pop()   # 中cur.val+= prepre = cur.valcur =cur.left       # 左return root

总结

二叉树这块的题目大部分可以通过递归和迭代两种方式来解决。
当遇到二叉搜索树时,可以利用其特性来简化代码。

对不同题目选择合适的遍历方式:

  • 涉及到二叉树的构造,无论普通二叉树还是二叉搜索树一定前序,都是先构造中节点。
  • 求普通二叉树的属性,一般是后序,一般要通过递归函数的返回值做计算。
  • 求二叉搜索树的属性,一定是中序了,要不白瞎了有序性了。

二叉树的遍历方式(递归和迭代)+层序遍历,必须要掌握。
要知道深度优先(前中后序遍历)和广度优先(层序遍历)对应哪些遍历方式。

关键是要掌握解决问题的方法,熟悉代码,理解题目。

二叉树的题就先做到这里,今天再看一下回溯算法的基础,明天开始做题。

相关文章:

代码随想录 - Day30 - 修剪二叉树,转换二叉树 + 二叉树总结

代码随想录 - Day30 - 修剪二叉树&#xff0c;转换二叉树 二叉树总结 669. 修剪二叉搜索树 有点像是删除二叉搜索树的变形&#xff0c;改变了删除条件而已。 递归法&#xff1a; class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> O…...

[音视频] sdl 渲染到外部创建的窗口上

API SDL_CreateWindowFrom # 在外部窗口上创建窗口 其他 api 调用&#xff0c;按照之前的 代码 ui.setupUi(this); sdl_width ui.label->width(); sdl_height ui.label->height(); SDL_Init(SDL_INIT_VIDEO); sdl_win SDL_CreateWindowFrom((void*)ui.label->wi…...

MongoDB之索引

大数据量使用全集合查询&#xff0c;这是非常影响性能的&#xff0c;而索引可以加快查询效率&#xff0c;提高性能&#xff0c;所以这方面的知识也是必不可少的。 查询分析 explain()可以帮助我们分析查询语句性能。 语法 db.collection.find(...).explain()案例及结果 案…...

Redis的介绍

Redis的架构介绍如下: 1. 概述 Redis是一个基于内存的高性能NoSQL键值数据库,支持网络访问和持久化特性。 2. 功能架构 Redis提供字符串、哈希、列表、集合、有序集合、位数组等多种数据结构,支持事务、Lua脚本、发布订阅、流水线等功能。 3. 技术架构 Redis使用单线程的…...

一文了解Docker的用法

一、什么是Docker Docker 是一个开源的应用容器引擎&#xff0c;基于 Go 语言 并遵从 Apache2.0 协议开源。 Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&#xff0c;也可以实现虚拟化。 容器是…...

netcat的使用

目录 netcat简介 nc的使用场景 nc实现通信 创建一个服务端 创建一个客户端 具体案例 环境 win10在具体路径下执行命令 win7在具体路径下执行命令 netcat文件传输 nc文件传输的利用 服务器等待接收文件 客户端向服务器发送文件 服务器向连接的客户端发送文件 客户…...

深度学习推荐系统(二)Deep Crossing及其在Criteo数据集上的应用

深度学习推荐系统(二)Deep Crossing及其在Criteo数据集上的应用 在2016年&#xff0c; 随着微软的Deep Crossing&#xff0c; 谷歌的Wide&Deep以及FNN、PNN等一大批优秀的深度学习模型被提出&#xff0c; 推荐系统全面进入了深度学习时代&#xff0c; 时至今日&#xff0c…...

前端常用 Vue3 项目组件大全

Vue.js 是一种流行的 JavaScript 前端框架&#xff0c;它简化了构建交互式的用户界面的过程。Vue3 是 Vue.js 的最新版本&#xff0c;引入了许多新的特性和改进。在 Vue3 中&#xff0c;组件是构建应用程序的核心部分&#xff0c;它们可以重用、组合和嵌套。下面是一些前端开发…...

javaee spring 静态代理

静态代理 package com.test.staticProxy;public interface IUsersService {public void insert(); }package com.test.staticProxy;//目标类 public class UsersService implements IUsersService {Overridepublic void insert() {System.out.println("添加用户");…...

Java 包装类和Arrays类(详细解释)

目录 包装类 作用介绍 包装类的特有功能 Arrays类 Arrays.fill() Arrays.toString() Arrays.sort() 升序排序 降序排序 Arrays.equals() Arrays.copyOf() Arrays.binarySearch() 包装类 作用介绍 包装类其实就是8种基本数据类型对应的引用类型。 基本数据类型引用…...

elementUi中的el-table表格的内容根据后端返回的数据用不同的颜色展示

效果图如下&#xff1a; 首先 首先&#xff1a;需要在表格行加入 <template slot-scope"{ row }"> </template>标签 <el-table-column prop"usable" align"center" label"状态" width"180" ><templ…...

在访问一个网页时弹出的浏览器窗口,如何用selenium 网页自动化解决?

相信大家在使用selenium做网页自动化时&#xff0c;会遇到如下这样的一个场景&#xff1a; 在你使用get访问某一个网址时&#xff0c;会在页面中弹出如上图所示的弹出框。 首先想到是利用Alert类来处理它。 然而&#xff0c;很不幸&#xff0c;Alert类处理的结果就是没有结果…...

python 基于http方式与基于redis方式传输摄像头图片数据的实现和对比

目录 0. 需求1. 基于http方式传递图片数据1.1 发送图片数据1.2 接收图片数据并可视化1.3 测试 2. 基于redis方式传递图片数据2.1 发送图片数据2.2 接收图片数据并可视化2.3 测试 3. 对比 0. 需求 在不同进程或者不同语言间传递摄像头图片数据&#xff0c;比如从java实现的代码…...

快速使用Git完整开发

本系列有两篇文章&#xff1a; 一是本篇&#xff0c;主要说明了关于Git工具的基础使用&#xff0c;包含三板斧&#xff08;git add、git commit、git push&#xff09;、Git基本配置、版本回退、分支管理、公钥与私钥、远端仓库和远端分支、忽略文件、命令别名、标签等内容。二…...

鲁棒优化入门(7)—Matlab+Yalmip两阶段鲁棒优化通用编程指南(下)

0.引言 上一篇博客介绍了使用Yalmip工具箱求解单阶段鲁棒优化的方法。这篇文章将和大家一起继续研究如何使用Yalmip工具箱求解两阶段鲁棒优化(默认看到这篇博客时已经有一定的基础了&#xff0c;如果没有可以看看我专栏里的其他文章)。关于两阶段鲁棒优化与列与约束生成算法的原…...

Docker技术--Docker中的网络问题

1.docker中的网络通信 如果想要弄清楚docker中的网络通信问题,其实需要弄清楚这几个问题就可以:容器与容器之间的通信、容器与外部网络之间的通信、外部网络与容器之间的通信。 -a:容器与容器之间的通信,如下所示: 在默认情况下,docker使用网桥(Bridge模式)与NAT通信。这…...

ASP.NET Core 中的两种 Web API

ASP.NET Core 有两种创建 RESTful Web API 的方式&#xff1a; 基于 Controller&#xff0c;使用完整的基于ControllerBase的基类定义接口endpoints。基于 Minimal APIs&#xff0c;使用Lambda表达式定义接口 endpoints。 基于 Controller 的 Web API 可以使用构造函数注入&a…...

【线程池】如何判断线程池中的任务执行完毕(三)

目录 前言 1. isTerminated()方法 2. awaitTermination()方法 3.getTaskCount()方法和executor.getCompletedTaskCount()方法结合使用 4.使用CountDownlatch类 前言 通常我们使用线程池的时候&#xff0c;系统处于运行的状态&#xff0c;而线程池本身就是主要为了线程复用&…...

Qt/C++编写视频监控系统81-Onvif报警抓图和录像并回放

一、前言 视频监控系统中的图文警情模块&#xff0c;是通过Onvif协议的事件订阅拿到的&#xff0c;通过事件订阅后&#xff0c;设备的各种报警事件比如入侵报警/遮挡报警/越界报警/开关量报警等&#xff0c;触发后都会主动往订阅者发送&#xff0c;而且一般都是会发送两次&…...

浅谈安防视频监控平台EasyCVR视频汇聚平台对于夏季可视化智能溺水安全告警平台的重要性

每年夏天都是溺水事故高发的时期&#xff0c;许多未成年人喜欢在有水源的地方嬉戏&#xff0c;这导致了悲剧的发生。常见的溺水事故发生地包括水库、水坑、池塘、河流、溪边和海边等场所。 为了加强溺水风险的提示和预警&#xff0c;完善各类安全防护设施&#xff0c;并及时发现…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...