代码随想录-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 是原始有序数组，left 和 right 分别表示当前子数组的左右边界索引。
    • 终止条件：如果 left > right，表示当前子数组为空，没有节点可构建，因此返回 null。
    • 选择根节点：为了构建高度平衡的BST，总是选择中间位置（或中间偏左，这里取中间下标 mid = (left + right) / 2）的元素作为根节点的值，这样做可以保证树尽量平衡。注意，当 left 和 right 为偶数时，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 是原始有序数组，left 和 right 分别表示当前考虑构建子树的数组范围。
    • 终止条件：当 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，加上 left 和 right 后除以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。

相关文章

随想录 Day 69 并查集 107. 寻找存在的路径

随想录 Day 69 并查集 107. 寻找存在的路径

随想录 Day 69 并查集 107. 寻找存在的路径 理论基础 int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
阅读更多...
uniapp接入微信小程序原生代码配置方案（优化版）

uniapp接入微信小程序原生代码配置方案（优化版）

uniapp项目需要把微信小程序原生语法的功能代码嵌套过来，无需把原生代码转换为uniapp，可以配置拷贝的方式集成过来 1、拷贝代码包到src目录 2、vue.config.js中配置原生代码包直接拷贝到编译目录中 3、pages.json中配置分包目录，原生入口组件的路径 4、manifest.json中配置分包，使用原生组件 5、需要把原生代码包里的页面修改成组件的方
阅读更多...
公共筛选组件（二次封装antd）支持代码提示

公共筛选组件（二次封装antd）支持代码提示

如果项目是基于antd组件库为基础搭建，可使用此公共筛选组件 使用到的库 npm i antdnpm i lodash-esnpm i @types/lodash-es -D /components/CommonSearch index.tsx import React from 'react';import { Button, Card, Form } from 'antd'
阅读更多...
17.用300行代码手写初体验Spring V1.0版本

17.用300行代码手写初体验Spring V1.0版本

1.1.课程目标 1、了解看源码最有效的方式，先猜测后验证，不要一开始就去调试代码。 2、浓缩就是精华，用 300行最简洁的代码 提炼Spring的基本设计思想。 3、掌握Spring框架的基本脉络。 1.2.内容定位 1、 具有1年以上的SpringMVC使用经验。 2、 希望深入了解Spring源码的人群，对 Spring有一个整体的宏观感受。 3、 全程手写实现SpringM
阅读更多...
代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...
记录AS混淆代码模板

记录AS混淆代码模板

开启混淆得先在build.gradle文件中把 minifyEnabled false改成true,以及shrinkResources true//去除无用的resource文件 这些是写在proguard-rules.pro文件内的 指定代码的压缩级别 -optimizationpasses 5 包明不混合大小写 -dontusemixedcaseclassnames 不去忽略非公共
阅读更多...
麻了！一觉醒来，代码全挂了。。

麻了！一觉醒来，代码全挂了。。

作为⼀名程序员，相信大家平时都有代码托管的需求。 相信有不少同学或者团队都习惯把自己的代码托管到GitHub平台上。 但是GitHub大家知道，经常在访问速度这方面并不是很快，有时候因为网络问题甚至根本连网站都打不开了，所以导致使用体验并不友好。 经常一觉醒来，居然发现我竟然看不到我自己上传的代码了。。 那在国内，除了GitHub，另外还有一个比较常用的Gitee平台也可以用于
阅读更多...
众所周知，配置即代码≠基础设置即代码

众所周知，配置即代码≠基础设置即代码

​前段时间翻到几条留言，问： “配置即代码和基础设施即代码一样吗？” “配置即代码是什么？怎么都是基础设施即代码？” 我们都是知道，DevOp的快速发展，让服务器管理与配置的时间大大减少，配置即代码和基础设施即代码作为DevOps的重要实践，在其中起到了关键性作用。 不少人将二者看作是一件事，配置即大代码是关于管理特定的应用程序配置设置本身，而基础设施即代码更关注的是部署支持应用程序环境所需的
阅读更多...
53、Flink Interval Join 代码示例

53、Flink Interval Join 代码示例

1、概述 interval Join 默认会根据 keyBy 的条件进行 Join 此时为 Inner Join； interval Join 算子的水位线会取两条流中水位线的最小值； interval Join 迟到数据的判定是以 interval Join 算子的水位线为基准； interval Join 可以分别输出两条流中迟到的数据-[sideOutputLeftLateData,
阅读更多...
Git代码管理的常用操作

Git代码管理的常用操作

在VS022中，Git的管理要先建立本地或远程仓库，然后commit到本地，最后push到远程代码库。 或者不建立本地的情况，直接拉取已有的远程代码。 Git是一个分布式版本控制系统，用于跟踪和管理文件的变化。它可以记录文件的修改历史，并且可以轻松地回滚到任何历史版本。 Git的基本概念包括： 仓库（Repository）：Git使用仓库来存储文件的版本历史。一个仓库可以包含多个文件
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2