欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

相关标签: python