当前位置: 首页 > 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的安…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

Qt的学习(一)

1.什么是Qt Qt特指用来进行桌面应用开发&#xff08;电脑上写的程序&#xff09;涉及到的一套技术Qt无法开发网页前端&#xff0c;也不能开发移动应用。 客户端开发的重要任务&#xff1a;编写和用户交互的界面。一般来说和用户交互的界面&#xff0c;有两种典型风格&…...