python数据结构(将有序数组转换为二叉搜索树)
程序员文章站
2023-11-30 17:54:58
将有序数组转换为二叉搜索树题目描述将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定有序数组: [-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树...
将有序数组转换为二叉搜索树
题目描述
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
思路
关键点:构造树时,二分法选择中间节点作为根节点,产生的树是平衡二叉树
python3实现
树节点的定义
class TreeNode: def __init__(self, x): self.val = x
self.left = None self.right = None
1.直接传入数组的一半当做子树进行递归
from typing import List
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
n = len(nums)
if n == 0:
return None
mid = n//2
root = TreeNode( nums[mid] )
root.left = self.sortedArrayToBST( nums[:mid] )
root.right = self.sortedArrayToBST( nums[mid+1:])
return root
2传入区间索引进行递归
from typing import List
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def midDivide(l,r):
if l > r:
return
mid = l + ( (r-l)>>1 )
root = TreeNode( nums[mid] )
root.left = midDivide(l, mid - 1)
root.right = midDivide(mid + 1, r)
return root
return midDivide(0,len(nums)-1)
本文地址:https://blog.csdn.net/qq_28757173/article/details/107100410