力扣 108 将有序数组转化为二叉搜索树

这篇具有很好参考价值的文章主要介绍了力扣 108 将有序数组转化为二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目描述:

代码部分:

(1)第一种方法

 (2)第二种方法

题目解析:

(1)复杂度与思想

(2)进阶分析:


题目描述:

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

代码部分:

(1)第一种方法

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 如果数组为空,返回 None
        if not nums:
            return None
        # 找到数组的中间位置
        mid = len(nums) // 2
        # 以中间位置的值为根节点创建一个二叉搜索树
        root = TreeNode(nums[mid])
        # 递归地将左半部分的数组转换为左子树
        root.left = self.sortedArrayToBST(nums[:mid])
        # 递归地将右半部分的数组转换为右子树
        root.right = self.sortedArrayToBST(nums[mid+1:])
        # 返回根节点
        return root

 (2)第二种方法

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) >> 1
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

题目解析:

(1)复杂度与思想

该代码的时间复杂度为 O(n),其中 n 为数组的长度。因为每个节点都会被遍历一次,且每次遍历的时间复杂度为 O(1)。

该题目涉及的知识点为二叉搜索树和递归。二叉搜索树是一种特殊的二叉树,它的左子树中的所有节点的值都小于根节点的值,右子树中的所有节点的值都大于根节点的值。递归是一种解决问题的方法,它将一个大问题分解成多个小问题,然后通过解决小问题来解决大问题。在该代码中,递归的思想被用来构建二叉搜索树。

(2)进阶分析:

本题要求将一个已经按升序排列的整数数组转换为一棵高度平衡的二叉搜索树。由于二叉搜索树的特性,我们可以通过二分法来构建一棵平衡的二叉搜索树。具体来说,我们可以选择数组的中间位置作为根节点,然后递归地构建左右子树。

具体实现上,我们定义一个递归函数 `sortedArrayToBST`,它接受一个整数数组 `nums` 作为参数,返回一棵高度平衡的二叉搜索树。如果 `nums` 为空,则返回空节点。否则,我们找到数组的中间位置 `mid`,将其作为根节点,然后递归地构建左右子树。左子树的数组范围是 `nums[:mid]`,右子树的数组范围是 `nums[mid+1:]`。递归的终止条件是数组为空。

代码实现上,我们可以使用 Python 的列表切片操作来获取子数组,然后递归调用 `sortedArrayToBST` 函数构建子树。最后返回根节点即可。

时间复杂度分析:每次递归都要对数组进行切片操作,时间复杂度为 $O(n)$,其中 $n$ 是数组的长度。由于每个节点都会被访问一次,因此总时间复杂度为 $O(n)$。

空间复杂度分析:每次递归都会创建一个新的节点,因此空间复杂度为 $O(n)$,其中 $n$ 是数组的长度。由于递归深度不超过 $\log n$,因此空间复杂度为 $O(\log n)$。

本题涉及的知识点包括二叉搜索树、递归、二分法等。二叉搜索树是一种常见的数据结构,它的特点是左子树的所有节点都小于根节点,右子树的所有节点都大于根节点。二分法是一种常见的算法思想,它可以用来在有序数组中查找元素、求解函数的零点等问题。递归是一种常见的算法实现方式,它可以用来解决树、图等数据结构的问题。

(3)二叉平衡树

二叉搜索树(Binary Search Tree,BST)是一种基于二叉树的数据结构,它具有以下特点:

1. 每个节点最多有两个子节点,左子节点的值小于父节点的值,右子节点的值大于父节点的值。

2. 对于任意节点,其左子树和右子树都是二叉搜索树。

3. 二叉搜索树的中序遍历是有序的。

二叉搜索树的主要应用是在查找、插入和删除操作中,它们的时间复杂度都是O(log n)。下面分别介绍这三个操作。

1. 查找操作

查找操作是指在二叉搜索树中查找某个节点。查找操作的过程是从根节点开始,如果目标节点的值小于当前节点的值,则在左子树中查找;如果目标节点的值大于当前节点的值,则在右子树中查找;如果目标节点的值等于当前节点的值,则找到了目标节点。如果查找到叶子节点仍然没有找到目标节点,则说明目标节点不存在于二叉搜索树中。

2. 插入操作

插入操作是指向二叉搜索树中插入一个新节点。插入操作的过程是从根节点开始,如果新节点的值小于当前节点的值,则在左子树中插入;如果新节点的值大于当前节点的值,则在右子树中插入。如果插入的位置已经存在节点,则更新该节点的值。

3. 删除操作

删除操作是指从二叉搜索树中删除一个节点。删除操作的过程比较复杂,需要考虑以下几种情况:

(1)如果要删除的节点是叶子节点,则直接删除该节点。

(2)如果要删除的节点只有一个子节点,则将该节点的子节点替换该节点。

(3)如果要删除的节点有两个子节点,则需要找到该节点的后继节点(即右子树中最小的节点),将后继节点的值复制到要删除的节点中,然后删除后继节点。

总结一下,二叉搜索树是一种非常重要的数据结构,它具有快速查找、插入和删除的优点。但是,二叉搜索树的性能取决于树的平衡性,如果树的高度过高,则操作的时间复杂度会退化为O(n),因此需要使用平衡二叉搜索树来解决这个问题。文章来源地址https://www.toymoban.com/news/detail-476719.html

到了这里,关于力扣 108 将有序数组转化为二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 热题 100 JavaScript--108. 将有序数组转换为二叉搜索树

    给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 按 严格递增 顺序排列

    2024年02月14日
    浏览(40)
  • LeetCode算法题解|​ 669. 修剪二叉搜索树​、108. 将有序数组转换为二叉搜索树、​538. 把二叉搜索树转换为累加树​

    题目链接:669. 修剪二叉搜索树 题目描述: 给你二叉搜索树的根节点  root  ,同时给定最小边界 low  和最大边界  high 。通过修剪二叉搜索树,使得所有节点的值在 [low, high] 中。修剪树  不应该  改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关

    2024年02月06日
    浏览(37)
  • 第23天-代码随想录刷题训练-第六章 ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

    - LeetCode 链接 给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。 修剪树不应该改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案

    2024年02月05日
    浏览(43)
  • HOT42-将有序数组转换为二叉搜索树

          leetcode原题链接 :将有序数组转换为二叉搜索树        上一篇 :HOT41-二叉树的层序遍历       下一篇 :HOT43-验证二叉搜索树         给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一

    2024年02月12日
    浏览(39)
  • 算法刷题Day 23 修剪二叉搜索树+将有序数组转换为二叉搜索树+把二叉搜索树转换为累加树

    递归 好神奇,完全凭感觉写,感觉应该过不了,结果就过了 具体是什么原理可以参考代码随想录的讲解 递归 迭代 使用三个队列来处理(感觉用三个栈也可以) 其实就是以右-中-左的顺序来处理二叉树 每次将当前节点加上上一次访问节点的新值 能想到保存前一次访问节点的

    2024年02月15日
    浏览(41)
  • 将有序数组转换为二叉树

    md这个破CSDN模板怎么没了,编辑器也死难用,气死 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 示例 2:

    2024年02月05日
    浏览(37)
  • 力扣0109——有序链表转换二叉搜索树

    难度: 中等 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-

    2024年02月21日
    浏览(37)
  • 力扣_数组26—合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,

    2024年01月21日
    浏览(44)
  • 【力扣】977. 有序数组的平方 <首尾指针>

    给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入 :nums = [-4,-1,0,3,10] 输出 :[0,1,9,16,100] 解释 :平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100] 示例 2: 输入 :nums = [-7,-3,2,3,11] 输出

    2024年02月14日
    浏览(30)
  • 力扣每日一题88:合并两个有序数组

    给你两个按  非递减顺序  排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nums1  和  nums2  中的元素数目。 请你  合并   nums2   到  nums1  中,使合并后的数组同样按  非递减顺序  排列。 注意: 最终,合并后数组不应由函数返回,而是存储在

    2024年02月07日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包