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

代码随想录算法训练营第二十二天丨 二叉树part09

669. 修剪二叉搜索树

思路

递归法

从图中可以看出需要重构二叉树,想想是不是本题就有点复杂了。

其实不用重构那么复杂。

在上图中我们发现节点0并不符合区间要求,那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了(就是把节点0从二叉树中移除),如图:

理解了最关键部分了我们再递归三部曲:

  • 确定递归函数的参数以及返回值

这里我们为什么需要返回值呢?

因为是要遍历整棵树,做修改,其实不需要返回值也可以,我们也可以完成修剪(其实就是从二叉树中移除节点)的操作。

但是有返回值,更方便,可以通过递归函数的返回值来移除节点。

这样的做法在二叉树:搜索树中的插入操作 (opens new window)和二叉树:搜索树中的删除操作 (opens new window)中大家已经了解过了。

代码如下:

TreeNode trimNode(TreeNode cur, int low, int high)
  • 确定终止条件

修剪的操作并不是在终止条件上进行的,所以就是遇到空节点返回就可以了。

if (cur == null){return null;
}
  • 确定单层递归的逻辑

如果root(当前节点)的元素小于low的数值,那么应该递归右子树,并返回右子树符合条件的头结点。

代码如下:

// 寻找符合区间[low, high]的节点
if (cur.val < low){TreeNode right = trimNode(cur.right, low, high);return right;
}

如果root(当前节点)的元素大于high的,那么应该递归左子树,并返回左子树符合条件的头结点。

代码如下:

if (cur.val > high){TreeNode left = trimNode(cur.left,low,high);return left;
}

接下来要将下一层处理完左子树的结果赋给root->left,处理完右子树的结果赋给root->right。

最后返回root节点,代码如下:

cur.left = trimNode(cur.left,low,high);//cur.left接入符合条件的左孩子
cur.right = trimNode(cur.right,low,high);//cur.right接入符合条件的右孩子
return cur;

此时大家是不是还没发现这多余的节点究竟是如何从二叉树中移除的呢?

在回顾一下上面的代码,针对下图中二叉树的情况:

669.修剪二叉搜索树1

如下代码相当于把节点0的右孩子(节点2)返回给上一层,

// 寻找符合区间[low, high]的节点
if (cur.val < low){TreeNode right = trimNode(cur.right, low, high);return right;
}

然后如下代码相当于用节点3的左孩子 把下一层返回的 节点0的右孩子(节点2) 接住。

cur.left = trimNode(cur.left,low,high);//cur.left接入符合条件的左孩子

此时节点3的左孩子就变成了节点2,将节点0从二叉树中移除了。

整体代码如下:

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {return trimNode(root,low,high);}TreeNode trimNode(TreeNode cur, int low, int high){if (cur == null){return null;}// 寻找符合区间[low, high]的节点if (cur.val < low){TreeNode right = trimNode(cur.right, low, high);return right;}if (cur.val > high){TreeNode left = trimNode(cur.left,low,high);return left;}cur.left = trimNode(cur.left,low,high);//cur.left接入符合条件的左孩子cur.right = trimNode(cur.right,low,high);//cur.right接入符合条件的右孩子return cur;}
}

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

思路

题目中说要转换为一棵高度平衡二叉搜索树。为什么强调要平衡呢?

因为只要给我们一个有序数组,如果强调平衡,都可以以线性结构来构造二叉搜索树。

例如 有序数组[-10,-3,0,5,9] 就可以构造成这样的二叉搜索树,如图。

上图中,是符合二叉搜索树的特性吧,如果要这么做的话,是不是本题意义就不大了,所以才强调是平衡二叉搜索树。

其实数组构造二叉树,构成平衡树是自然而然的事情,因为大家默认都是从数组中间位置取值作为节点元素,一般不会随机取。所以想构成不平衡的二叉树是自找麻烦

本质就是寻找分割点,分割点作为当前节点,然后递归左区间和右区间

分割点就是数组中间位置的节点。

那么为问题来了,如果数组长度为偶数,中间节点有两个,取哪一个?

取哪一个都可以,只不过构成了不同的平衡二叉搜索树。

例如:输入:[-10,-3,0,5,9]

如下两棵树,都是这个数组的平衡二叉搜索树:

如果要分割的数组长度为偶数的时候,中间元素为两个,是取左边元素 就是树1,取右边元素就是树2。

递归

递归三部曲:

  • 确定递归函数返回值及其参数

删除二叉树节点,增加二叉树节点,都是用递归函数的返回值来完成,这样是比较方便的。

相信大家如果仔细看了二叉树:搜索树中的插入操作 (opens new window)和二叉树:搜索树中的删除操作 (opens new window),一定会对递归函数返回值的作用深有感触。

那么本题要构造二叉树,依然用递归函数的返回值来构造中节点的左右孩子。

再来看参数,首先是传入数组,然后就是左下标left和右下标right,我们在二叉树:构造二叉树登场! (opens new window)中提过,在构造二叉树的时候尽量不要重新定义左右区间数组,而是用下标来操作原数组

所以代码如下:

// 左闭右闭区间[left, right]
TreeNode sortTree(int[] nums,int left,int right)

这里注意,我这里定义的是左闭右闭区间,在不断分割的过程中,也会坚持左闭右闭的区间,这又涉及到我们讲过的循环不变量

  • 确定递归终止条件

这里定义的是左闭右闭的区间,所以当区间 left > right的时候,就是空节点了。

代码如下:

if (left > right){return null;}
  • 确定单层递归的逻辑

首先取数组中间元素的位置,不难写出int mid = (left + right) / 2;这么写其实有一个问题,就是数值越界,例如left和right都是最大int,这么操作就越界了,在二分法 (opens new window)中尤其需要注意!

所以可以这么写:int mid = left + ((right - left) / 2);

但本题leetcode的测试数据并不会越界,所以怎么写都可以。但需要有这个意识!

取了中间位置,就开始以中间位置的元素构造节点,代码:TreeNode cur = new TreeNode(nums[mid]); 。

接着划分区间,root的左孩子接住下一层左区间的构造节点,右孩子接住下一层右区间构造的节点。

最后返回root节点,单层递归整体代码如下:

int mid = (left+right) /2;
TreeNode cur = new TreeNode(nums[mid]);
cur.left = sortTree(nums,left,mid-1);
cur.right = sortTree(nums,mid+1,right);
return cur;
  • 递归整体代码如下:
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return sortTree(nums,0, nums.length-1);}// 左闭右闭区间[left, right]TreeNode sortTree(int[] nums,int left,int right){if (left > right){return null;}int mid = (left+right) /2;TreeNode cur = new TreeNode(nums[mid]);cur.left = sortTree(nums,left,mid-1);cur.right = sortTree(nums,mid+1,right);return cur;}
}

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

思路

如何累加?遇到一个节点,然后再遍历其他节点累加?

然后再发现这是一棵二叉搜索树,二叉搜索树啊,这是有序的啊。

那么有序的元素如何求累加呢?

其实这就是一棵树,大家可能看起来有点别扭,换一个角度来看,这就是一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13],是不是感觉这就简单了。

为什么变成数组就是感觉简单了呢?

因为数组大家都知道怎么遍历啊,从后向前,挨个累加就完事了,这换成了二叉搜索树,看起来就别扭了一些是不是。

那么知道如何遍历这个二叉树,也就迎刃而解了,从树中可以看出累加的顺序是右中左,所以我们需要反中序遍历这个二叉树,然后顺序累加就可以了

#递归

遍历顺序如图所示:

本题依然需要一个pre指针记录当前遍历节点cur的前一个节点,这样才方便做累加。

pre指针的使用技巧,在二叉树:搜索树的最小绝对差 (opens new window)和二叉树:我的众数是多少? (opens new window)都提到了,这是常用的操作手段。

  • 递归函数参数以及返回值

这里很明确了,不需要递归函数的返回值做什么操作了,要遍历整棵树。

同时需要定义一个全局变量pre,用来保存cur节点的前一个节点的数值。

代码如下:

// 记录前一个节点的数值
TreeNode pre = new TreeNode(0);
  • 确定终止条件

遇空就终止。

if (node == null){return null;
}
  • 确定单层递归的逻辑

注意要右中左来遍历二叉树, 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。

代码如下:

//右
sumTree(node.right);
//中
node.val = node.val + pre.val;
pre = node;
//左
sumTree(node.left);return node;

递归法整体代码如下:

class Solution {public TreeNode convertBST(TreeNode root) {return sumTree(root);}// 记录前一个节点的数值TreeNode pre = new TreeNode(0);//右中左TreeNode sumTree(TreeNode node){if (node == null){return null;}//右sumTree(node.right);//中node.val = node.val + pre.val;pre = node;//左sumTree(node.left);return node;}
}

以上为我做题时候的相关思路,自己的语言组织能力较弱,很多都是直接抄卡哥的,有错误望指正。

相关文章:

代码随想录算法训练营第二十二天丨 二叉树part09

669. 修剪二叉搜索树 思路 递归法 从图中可以看出需要重构二叉树&#xff0c;想想是不是本题就有点复杂了。 其实不用重构那么复杂。 在上图中我们发现节点0并不符合区间要求&#xff0c;那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了&#xff08;就是把节点…...

Apipost连接数据库详解

Apipost提供了数据库连接功能&#xff0c;在接口调试时可以使用数据库获取入参或进行断言校验。目前的Apipost支持&#xff1a;Mysql、SQL Sever、Oracle、Clickhouse、达梦数据库、PostgreSQL、Redis、MongoDB 8种数据库的连接操作 新建数据库连接&#xff1a; 在「项目设置…...

让 Visual Studio 用上 ChatGPT

一、简介 Visual chatGPT Studio 是 Visual Studio 的一个免费扩展&#xff0c;它直接在 IDE 中添加了 chatGPT 功能。它允许用户以可以根据菜单功能的方式使用 chatGPT。 二、功能介绍 该扩展提供了一组使用 ChatGPT 命令&#xff0c;可以在编辑器中选择你需要处理的代码或…...

如何删除错误堆栈里的数据

修改某个主数据。然后发现N年前&#xff0c;某位开发在DTP上做了一个错误堆栈。 这里面有很多历史错误信息&#xff0c;有几千条了&#xff0c;一条条删肯定不可能。 如果不删除&#xff0c;DTP增量无法激活&#xff0c;明天处理链肯定出问题。 于是找到一位印度大神的方法&a…...

k8s使用minio分布式集群作为存储--基础配置篇

背景:minio分布式集群是单独的服务,并没有被k8s管理,k8s与minio集群在不同的服务器上部署,k8s需要使用minio分布式集群作为k8s集群的配置文件及其他文件的存储介质。 1、安装fuse: sudo yum install fuse1.1查询是否有fusemount3 sudo find / -name fusermount31.2确认…...

@Autowired 到底是怎么把变量注入进来的?

[toc] 在 Spring 容器中&#xff0c;当我们想给某一个属性注入值的时候&#xff0c;有多种不同的方式&#xff0c;例如可以通过构造器注入、可以通过 set 方法注入&#xff0c;也可以使用 Autowired、Inject、Resource 等注解注入。 今天我就来和小伙伴们聊一聊&#xff0c;Au…...

【Python学习笔记】函数

1. 函数组成 Python中&#xff0c;我们是这样定义函数的&#xff1a; def function(para1, para2):print("func start")print(para1)print(para2)print("func end")print("让技术总监面试 求职者")return "func return"def 是关键字…...

简单实现一个todoList(上移、下移、置顶、置底)

演示 html部分 <!DOCTYPE html> <html> <head><title>表格示例</title> </head> <body><table border"1"><thead><tr><th>更新时间</th><th>操作</th></tr></thead…...

计算机视觉:池化层的作用是什么?

本文重点 在深度学习中,卷积神经网络(CNN)是一种非常强大的模型,广泛应用于图像识别、目标检测、自然语言处理等领域。而池化层作为CNN中的一个关键步骤,扮演着优化神经网络、提升深度学习性能的重要角色。本文将深入探讨池化层的作用及其重要性,帮助读者更好地理解和应…...

luffy项目前端创建、配置、解决跨域问题、后端数据库迁移

前端 创建前端vue 使用vue-cil创建前端将无用的东西删除 ​配置 跟后端交互&#xff1a;axios 安装插件&#xff1a;cnpm install -S axios在main.js中写import axios from "axios"; Vue.prototype.$axios axios后续使用就直接this.$axios即可 操作cookie&am…...

电商数据API接口:新服务下电商网站、跨境电商独立站,移动APP的新型拉新武器

互联网的发展改变了我们的生活方式&#xff0c;也改变了企业商家们的营销方式&#xff0c;越来越多的企业商家把产品营销从线下转到线上&#xff0c;选择在线商城、移动APP、微信公众号等互联网工具进行营销活动。而随着营销模式的多元化和电子支付渠道的进一步发展&#xff0c…...

多线程并发篇---第十一篇

系列文章目录 文章目录 系列文章目录前言一、CAS的原理二、CAS有什么缺点吗?三、引用类型有哪些?有什么区别?前言 一、CAS的原理 CAS叫做CompareAndSwap,比较并交换,主要是通过处理器的指令来保证操作的原子性,它包含 三个操作数: 变量内存地址,V表示旧的预期值,A表示…...

JVM第六讲:JVM 基础 - Java 内存模型引入

JVM 基础 - Java 内存模型引入 很多人都无法区分Java内存模型和JVM内存结构&#xff0c;以及Java内存模型与物理内存之间的关系。本文是JVM第六讲&#xff0c;从堆栈角度引入JMM&#xff0c;然后介绍JMM和物理内存之间的关系, 为后面JMM详解, JVM 内存结构详解, Java 对象模型详…...

机房安全管理制度

#安全运维管理制度# 1、总则 1.1、目的 为进一步规范XXXXX单位机房安全管理工作&#xff0c;防止未经授权的访问&#xff0c;做好机房的防火、防盗等工作&#xff0c;确保XXXXX单位机房物理设施的安全&#xff0c;制定本制度。 1.2、范围 本制度适用于XXXXX单位机房的安全…...

【自然语言处理】— 隐马尔可夫模型详解、例解

【自然语言处理】— 隐马尔可夫模型 【自然语言处理】— 隐马尔可夫模型引例隐马尔可夫模型概念隐马尔可夫模型的关键隐马尔可夫模型的数学表示隐含状态与观测结果状态转移矩阵观测概率矩阵初始状态概率向量 小结 【自然语言处理】— 隐马尔可夫模型 引例 假设有三种不同的骰…...

运行的 akrun 会打印信息到控制台,如何取消打印 -- chatGPT

gpt: 如果运行的程序 akrun 打印信息到控制台&#xff0c;但您希望取消或禁止它的输出&#xff0c;可以尝试以下方法&#xff1a; 1. **重定向输出到空文件**&#xff1a;您可以将程序的标准输出重定向到一个空文件&#xff0c;从而禁止信息输出到控制台。执行以下命令&#…...

【React】03-React面向组件编程2

文章目录 2.6. 组件的生命周期2.6.1. 效果2.6.2. 理解2.6.3. 生命周期流程图(旧)2.6.4. 生命周期流程图(新)2.6.5. 重要的勾子2.6.6. 即将废弃的勾子2.6.7 getSnapshotBeforeUpdate 2.7. 虚拟DOM与DOM Diffing算法2.7.1. 效果2.7.2. 基本原理图 2.6. 组件的生命周期 2.6.1. 效…...

【python编程】python无法import模块的一种原因分析

python系统路径添加错误 报错原因原因分析解决办法补充 最近写代码的时候遇到一个问题&#xff0c;就是想添加工程下fu_convert文件夹下自己编写的convert_fw.py模块&#xff0c;但是出现报错&#xff0c;是个比较低级的问题&#xff0c;但还是简单记录一下 报错原因 无法找到…...

vue3.0与vue2.0的区别

前言 Vue 3.0是一个用于构建用户界面的JavaScript框架。相比于Vue 2.x&#xff0c;Vue 3.0在性能、体积和开发体验上都有了很大的提升。 以下将从不同的角度上去分析Vue 3.0与Vue 2.0的区别&#xff1a; 一、项目架构 从项目搭建和打包工具的选择来看&#xff1a; Vue 2.0 中…...

09_Webpack打包工具

1 初识Webpack 1.1 什么是Webpack Webpack打包工具对项目中的复杂文件进行打包处理&#xff0c;可以实现项目的自动化构建&#xff0c;并且给前端开发人员带来了极大的便利。 目前&#xff0c;企业中的绝大多数前端项目是基于Webpack打包工具来进行开发的。 1.2 Webpack的安…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...