python数据结构(将有序数组转换为二叉搜索树)
程序员文章站
2022-10-19 13:09:08
1、题目描述https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树(BST)。本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。2、代码详解附:此题提交时必须注释掉class TreeNode类法一:中序遍历,总是选择中间位置左边的数字作为根节点# Definition for ....
1、题目描述
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树(BST)。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
2、代码详解
附:此题提交时必须注释掉class TreeNode类
法一:中序遍历,总是选择中间位置左边的数字作为根节点
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def helper(left, right):
if left > right:
return None
# 总是选择中间位置左边的数字作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1) # 写成helper返回
时间复杂度:O(n),其中 n 是数组的长度。每个数字只访问一次。
空间复杂度:O(logn),其中 n 是数组的长度。空间复杂度不考虑返回值,因此空间复杂度主要取决于递归栈的深度,递归栈的深度是 O(logn)。
二叉搜索树的中序遍历结果为递增序列。现在题目给了我们一个递增序列,要求我们构造一棵二叉搜索树,就是要实现这一特性的逆过程。
中序遍历的顺序为:左节点 → 根节点 → 右节点。
构造一棵树的过程可以拆分成无数个这样的子问题:构造树的每个节点以及节点之间的关系。对于每个节点来说,都需要:
- 选取节点
- 构造该节点的左子树
- 构造该节点的右子树
要求构造一棵「高度平衡」的树,所以我们在选取节点时选择数组的中点作为根节点,以此来保证平衡性。
法一类似写法(没写helper函数)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums):
if not nums:
return None
# 找到中点作为根节点
mid = len(nums) // 2
node = TreeNode(nums[mid])
# 左侧数组作为左子树
left = nums[:mid]
right = nums[mid+1:]
# 递归调用
node.left = self.sortedArrayToBST(left)
node.right = self.sortedArrayToBST(right)
return node
本文地址:https://blog.csdn.net/IOT_victor/article/details/107111399
下一篇: 数据结构(二叉树的层序遍历)