算法训练Day23|669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

简介: 算法训练Day23|669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

LeetCode:669. 修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣(LeetCode)


1.思路

修剪就是根据指定区间进行符合条件的递归。位于区间两侧的往区间内靠拢,也即小于low时,向右遍历并返回节点,大于high时,向左遍历并返回节点。位于区间内时,遍历该节点的左右子树。


2.代码实现

 1class Solution {
 2    public TreeNode trimBST(TreeNode root, int low, int high) {
 3        // 递归法遍历整棵树
 4        // 当节点值不介于low和high之间时,返回null
 5        if (root == null) return null;
 6        // 小于时向右遍历
 7        if (root.val < low) {
 8            return trimBST(root.right, low, high);
 9        } else if (root.val > high) { // 大于时,向左遍历
10            return trimBST(root.left, low, high);
11        } 
12        // 介于之间时,遍历该节点下的所有节点
13        root.left = trimBST(root.left, low, high);
14        root.right = trimBST(root.right, low, high);
15        return root;
16    }
17}

3.复杂度分析

时间复杂度:O(n).至多遍历整棵树,量级为O(n).

空间复杂度:O(n).调用递归函数的深度即为栈的开销,最坏的情况是当二叉搜索树为链表。


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

108. 将有序数组转换为二叉搜索树 - 力扣(LeetCode)


1.思路

选取数组中间节点元素作为根节点,分别对其进行左右遍历构建该节点的左右子树,返回即可。

存在问题:逻辑挺清晰的,实现有难度,下次硬干。。。


2.代码实现

 1class Solution {
 2    public TreeNode sortedArrayToBST(int[] nums) {
 3
 4        // 调用辅助函数,传入数组和数组的边界索引
 5        return sortedArrayToBST(nums, 0, nums.length);
 6    }
 7
 8    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
 9        // 如果左边界>=右边界,表示没有元素,返回null
10        if (left >= right) {
11            return null;
12        }
13        // 如果只有一个元素,创建节点,将元素加入节点中,并返回节点
14        if (right - left == 1) {
15            return new TreeNode(nums[left]);
16        }
17        // 如果有多个元素,中间向两侧遍历、创建节点、赋值
18        int mid = left + (right - left) / 2;
19        TreeNode root = new TreeNode(nums[mid]);
20        // 构建该节点的左子树
21        root.left = sortedArrayToBST(nums, left, mid);
22        // 构建该节点的右子树
23        root.right = sortedArrayToBST(nums, mid + 1, right);
24        return root;
25    }
26}

3.复杂度分析

时间复杂度:时间消耗取决于递归函数的调用次数,而调用递归函数的次数为O(n).

空间复杂度:取决于栈的开销,栈的开销取决于递归函数的调用深度,O(n/2).


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

538. 把二叉搜索树转换为累加树 - 力扣(LeetCode)


1.思路

利用二叉搜索树的左中右升序的特性,该题是从右至左累加,所以遍历顺序采用右——中——左进行。定义全局变量sum,将该值赋给相应的节点即可。


2.代码实现

 1class Solution {
 2    int sum; // 声明全局变量
 3    public TreeNode convertBST(TreeNode root) {
 4        convertBST1(root);
 5        return root;
 6    }
 7    // 单层递归逻辑
 8    public void convertBST1(TreeNode root) {
 9        // 终止条件
10        if (root == null) {
11            return;
12        }
13        convertBST1(root.right);
14        sum += root.val;
15        root.val = sum;
16        convertBST1(root.left);
17    }
18}

3.复杂度分析

时间复杂度:O(n).

空间复杂度:调用函数消耗的空间为栈空间的消耗,因此空间消耗取决于递归函数的调用层数或者深度。最坏情况是链表,则空间复杂度为O(n).


相关文章
|
7月前
|
机器学习/深度学习 存储 算法
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
|
4月前
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty  敏感词
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
142 17
|
4月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
124 7
|
4月前
|
存储 监控 算法
公司内部网络监控中的二叉搜索树算法:基于 Node.js 的实时设备状态管理
在数字化办公生态系统中,公司内部网络监控已成为企业信息安全管理体系的核心构成要素。随着局域网内终端设备数量呈指数级增长,实现设备状态的实时追踪与异常节点的快速定位,已成为亟待解决的关键技术难题。传统线性数据结构在处理动态更新的设备信息时,存在检索效率低下的固有缺陷;而树形数据结构因其天然的分层特性与高效的检索机制,逐渐成为网络监控领域的研究热点。本文以二叉搜索树(Binary Search Tree, BST)作为研究对象,系统探讨其在公司内部网络监控场景中的应用机制,并基于 Node.js 平台构建一套具备实时更新与快速查询功能的设备状态管理算法框架。
133 3
|
6月前
|
人工智能 算法 语音技术
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
清华大学与腾讯联合推出的Video-T1技术,通过测试时扩展(TTS)和Tree-of-Frames方法,显著提升视频生成的连贯性与文本匹配度,为影视制作、游戏开发等领域带来突破性解决方案。
204 4
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
157 3
 算法系列之数据结构-Huffman树
|
6月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
191 22
|
6月前
|
存储 监控 算法
基于 PHP 二叉搜索树算法的内网行为管理机制探究
在当今数字化网络环境中,内网行为管理对于企业网络安全及高效运营具有至关重要的意义。它涵盖对企业内部网络中各类行为的监测、分析与管控。在内网行为管理技术体系里,算法与数据结构扮演着核心角色。本文将深入探究 PHP 语言中的二叉搜索树算法于内网行为管理中的应用。
69 4
|
7月前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。

热门文章

最新文章