代码随想录-Day23

2024-05-30 01:20
文章标签 随想录 代码 day23

本文主要是介绍代码随想录-Day23,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

669. 修剪二叉搜索树

在这里插入图片描述

方法一:递归

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) {return null;}if (root.val < low) {return trimBST(root.right, low, high);} else if (root.val > high) {return trimBST(root.left, low, high);} else {root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}}
}

这段代码定义了一个名为 Solution 的类,其中包含一个方法 trimBST,用于修剪(裁剪)给定二叉搜索树(BST)中的节点,使得所有节点的值在指定的区间 [low, high] 内。修剪操作应当保持二叉搜索树的性质。以下是代码逻辑的详细解析:

  1. 基本情况处理:首先检查根节点 root 是否为空。如果为空,直接返回 null,因为没有节点需要修剪。

  2. 节点值处理

    • 如果当前节点 root 的值 root.val 小于 low,说明当前节点及其左子树都不可能在保留范围内,因此直接递归地对右子树 root.right 调用 trimBST 方法,并返回结果作为新的根节点。这一步相当于“跳过”当前节点及其左子树。
    • 如果当前节点 root 的值 root.val 大于 high,说明当前节点及其右子树都不可能在保留范围内,因此直接递归地对左子树 root.left 调用 trimBST 方法,并返回结果作为新的根节点。这一步相当于“跳过”当前节点及其右子树。
    • 如果当前节点的值满足 low <= root.val <= high,说明当前节点值在指定区间内,需要保留。此时,递归地对左右子树进行修剪,并保持当前节点作为修剪后子树的根节点。
  3. 递归修剪子树:当当前节点值符合条件需要保留时,分别对左子树 root.left 和右子树 root.right 递归调用 trimBST 方法,以确保整个子树都被正确修剪。

  4. 返回处理后的节点:经过上述处理后,直接返回当前处理过的节点 root,作为修剪后子树的根。递归过程中,这个返回值会被上一层调用用来构建整个修剪后的BST。

通过这样的递归逻辑,trimBST 方法能够从根节点开始,逐步构建出只包含值在 [low, high] 范围内的二叉搜索树,并保持BST的性质。不在范围内的节点及其子树都会被“剪掉”,从而实现高效的修剪操作。

方法二:迭代

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {while (root != null && (root.val < low || root.val > high)) {if (root.val < low) {root = root.right;} else {root = root.left;}}if (root == null) {return null;}for (TreeNode node = root; node.left != null; ) {if (node.left.val < low) {node.left = node.left.right;} else {node = node.left;}}for (TreeNode node = root; node.right != null; ) {if (node.right.val > high) {node.right = node.right.left;} else {node = node.right;}}return root;}
}

这段代码提供了另一种实现方式,使用迭代方法来修剪二叉搜索树(BST),使其所有节点的值落在指定区间 [low, high] 内。相较于递归方法,迭代方法直接利用循环进行遍历和修剪。以下是代码逻辑的详细解析:

  1. 初始化:首先,代码通过一个 while 循环找到BST的第一个(最左边的)落在指定区间 [low, high] 内的节点作为新的根节点。如果根节点 root 的值小于 low,则向右移动(因为BST的性质保证了所有左子节点的值都小于根节点,所以要找大于等于 low 的节点,只能往右走);如果根节点的值大于 high,则向左移动。如果整个树的所有节点都不在区间内,最终 root 会变成 null,直接返回 null

  2. 修剪左子树:接下来,使用一个 for 循环来修剪根节点的左子树。循环的条件是当前节点的左子节点不为空。如果左子节点的值小于 low,说明整个左子树都不在指定区间内,直接将当前节点的左子节点更新为其左子节点的右子节点(跳过整个左子树的左部分);否则,将当前节点更新为其左子节点,继续检查更左的节点。

  3. 修剪右子树:随后,再使用一个类似的 for 循环来修剪根节点的右子树。循环的条件是当前节点的右子节点不为空。如果右子节点的值大于 high,说明整个右子树的右部分都不在指定区间内,直接将当前节点的右子节点更新为其右子节点的左子节点(跳过整个右子树的右部分);否则,将当前节点更新为其右子节点,继续检查更右的节点。

  4. 返回修剪后的根节点:经过上述两步修剪后,根节点及其左右子树都已经满足条件,直接返回 root 作为修剪后的二叉搜索树的根。

这种迭代方法同样保持了BST的性质,并且在处理每个节点时都是常量时间复杂度,总体时间复杂度为O(N),其中N为树中的节点数,空间复杂度为O(1),因为它只使用了固定数量的指针变量。

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

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵
平衡二叉搜索树。

方法一:中序遍历,总是选择中间位置左边的数字作为根节点

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1);}public TreeNode helper(int[] nums, int left, int right) {if (left > right) {return null;}// 总是选择中间位置左边的数字作为根节点int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}

这段代码定义了一个名为 Solution 的类,其中包含两个方法,用于将一个有序数组(升序)转换成一棵高度平衡的二叉搜索树(BST)。二叉搜索树的特性是左子树所有节点的值小于根节点的值,右子树所有节点的值大于根节点的值,且每个节点的左、右子树也分别是BST。下面是代码的详细解析:

  1. sortedArrayToBST(int[] nums) 方法:这是主要的接口方法,接收一个有序数组 nums 作为参数,然后调用辅助方法 helper 来完成转换工作,最终返回构建好的BST的根节点。

  2. helper(int[] nums, int left, int right) 方法:这是一个递归辅助方法,用于实际构建BST。

    • 输入参数nums 是原始有序数组,leftright 分别表示当前子数组的左右边界索引。
    • 终止条件:如果 left > right,表示当前子数组为空,没有节点可构建,因此返回 null
    • 选择根节点:为了构建高度平衡的BST,总是选择中间位置(或中间偏左,这里取中间下标 mid = (left + right) / 2)的元素作为根节点的值,这样做可以保证树尽量平衡。注意,当 leftright 为偶数时,mid 实际上取的是中间两个数中左边的那个。
    • 递归构建左右子树:以 mid 为界,分别对左半部分 [left, mid - 1] 和右半部分 [mid + 1, right] 递归调用 helper 方法,构建当前节点的左子树和右子树。
    • 返回根节点:构建好左右子树后,返回当前子树的根节点。

通过这样的递归划分,每个子数组都会被处理成一个高度平衡的BST子树,最终整个数组转换成了一棵高度平衡的二叉搜索树。这种方法充分利用了有序数组的特性,保证了构建的BST不仅是正确的,而且高度平衡,提高了树的查询效率。

方法二:中序遍历,总是选择中间位置右边的数字作为根节点

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1);}public TreeNode helper(int[] nums, int left, int right) {if (left > right) {return null;}// 总是选择中间位置右边的数字作为根节点int mid = (left + right + 1) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}

这段代码与之前提供的解决方案非常相似,都是将一个有序数组(升序)转换为一棵高度平衡的二叉搜索树(BST)。主要区别在于选取中间元素的方式:之前的解决方案选取中间位置左边的数字作为根节点,而这里的代码选择的是中间位置右边的数字。下面是代码解析:

  1. sortedArrayToBST(int[] nums) 方法:此方法作为接口,接收一个有序数组 nums,然后调用辅助方法 helper 来构建平衡BST,并返回根节点。

  2. helper(int[] nums, int left, int right) 方法:这是一个递归辅助方法,用于递归构建BST。

    • 输入参数nums 是原始有序数组,leftright 分别表示当前考虑构建子树的数组范围。
    • 终止条件:当 left > right 时,表示当前区间为空,无需构建节点,直接返回 null
    • 选择根节点:与之前版本不同,这里通过 (left + right + 1) / 2 计算中间索引,目的是选择区间的中间位置右边的数作为根节点。这确保了当数组长度为奇数时,中间值取右侧;偶数时,同样偏向取右侧的值作为根。
    • 递归构建子树:基于选定的根节点值,分别对左半区间 [left, mid - 1] 和右半区间 [mid + 1, right] 递归调用 helper 方法,构建当前节点的左子树和右子树。
    • 返回根节点:构建完左右子树后,返回当前子树的根节点。

通过这样的递归过程,整个数组被均衡地分割并构建为一棵高度平衡的BST,其中每个节点的值都来自数组中的一个位置,且树保持了BST的性质(左子树所有节点值小于根节点值,右子树所有节点值大于根节点值)。选择中间偏右的元素作为根节点是实现平衡的一种方式,虽不如选取正中间那样绝对平衡,但在大多数情况下能保持较好的平衡性。

方法三:中序遍历,选择任意一个中间位置数字作为根节点

class Solution {Random rand = new Random();public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1);}public TreeNode helper(int[] nums, int left, int right) {if (left > right) {return null;}// 选择任意一个中间位置数字作为根节点int mid = (left + right + rand.nextInt(2)) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}

这段代码依然致力于将一个有序数组(升序)转换为一棵高度平衡的二叉搜索树(BST),但与之前的实现有所不同,它在选择中间元素作为根节点时引入了随机性,以提高算法在特定输入下的性能表现。下面是代码的详细解析:

  1. 类成员变量:定义了一个 Random 类型的成员变量 rand,用于生成随机数。

  2. sortedArrayToBST(int[] nums) 方法:此方法与之前的实现相同,作为对外接口,接收有序数组并调用 helper 方法构建BST。

  3. helper(int[] nums, int left, int right) 方法:这个递归辅助方法负责实际的转换工作,其参数含义也保持一致。不同之处在于如何选择中间元素:

    • 随机选择中间位置:这里使用公式 (left + right + rand.nextInt(2)) / 2 来确定中间位置的索引。rand.nextInt(2) 会返回0或1,加上 leftright 后除以2,实质上会在左侧的中间位置和右侧的中间位置之间随机选择一个索引作为根节点。这种方法在理论上可以避免在特定输入数据下构造出极端不平衡的BST,比如当有序数组本身就是近乎有序的情况下,传统的总是选择中间位置作为根节点的方法可能导致构造出来的BST极度倾斜。通过随机化选择,可以使得构造的BST在统计学意义上更加平衡,提高树的操作效率,如查找、插入等。
  4. 构建左右子树:与之前的实现相同,根据选定的中间位置索引,递归地构建当前节点的左子树和右子树。

通过这种方式,尽管每次运行时可能生成不同的BST(因为根节点的选择是随机的),但整体上仍然能保证构建出的BST高度平衡,同时在一定程度上优化了在特定输入下的性能表现,特别是对于那些可能导致递归方法偏向构建非平衡树的特殊排序数组。

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

反序中序遍历

class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {if (root != null) {convertBST(root.right);sum += root.val;root.val = sum;convertBST(root.left);}return root;}
}

这段代码定义了一个名为 Solution 的类,其中包含一个方法 convertBST,该方法旨在将一个二叉搜索树(BST)转换成一个累加树。累加树是一种特殊的二叉树,其中每个节点的值等于原来的节点值加上所有大于它的节点值(在原BST中)。具体实现细节如下:

  • 类成员变量:

    • sum:这是一个整型成员变量,初始化为0,用于在遍历过程中累加节点值。
  • convertBST(TreeNode root) 方法

    • 输入参数:root 是二叉搜索树的根节点。
    • 返回值:返回转换后的二叉搜索树的根节点,现在它变成了一棵累加树。

方法内部逻辑遵循后序遍历的顺序(右子树 -> 根节点 -> 左子树),这是解决此类问题的关键,原因如下:

  1. 先遍历右子树:由于BST的性质(左子树的所有节点小于根节点,右子树的所有节点大于根节点),先访问右子树意味着我们从最大的节点开始累加,这符合累加树的要求。
  2. 累加当前节点值:在访问完当前节点的右子树后,将当前节点的值与已累加的值相加,然后更新当前节点的值。
  3. 遍历左子树:最后遍历左子树,这样在访问左子树的每个节点时,它们都会得到已经更新过的父节点及父节点右边所有节点的累加和。

通过这样的递归过程,整个BST被转换成了累加树,且每个节点的值都正确反映了累加的规则。最后,该方法返回转换后的树的根节点。

这篇关于代码随想录-Day23的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

husky 工具配置代码检查工作流:提交代码至仓库前做代码检查

提示:这篇博客以我前两篇博客作为先修知识,请大家先去看看我前两篇博客 博客指路:前端 ESlint 代码规范及修复代码规范错误-CSDN博客前端 Vue3 项目开发—— ESLint & prettier 配置代码风格-CSDN博客 husky 工具配置代码检查工作流的作用 在工作中,我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库,显然是不合理的 所

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码,例如: using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can