Convert Sorted Array to Binary Search Tree(有序列表转化为BST)

2,437次阅读
没有评论

共计 865 个字符,预计需要花费 3 分钟才能阅读完成。

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解法:

BST构建的思路是选取中间的数据作为节点,然后一份为2,在左右部分继续寻找新的节点,这一看就是采用二分法的思想
这在快速排序,还有二分查找中经常遇到的。

# 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: List[int]) -> TreeNode:
        #构造节点
        def _node(value,left,right):
            node=TreeNode(value)
            node.left=left
            node.right=right
            return node
        
        def construct_tree(l,r):
            #类似分而治之的方法
            mid=(l+r)//2
            if l>r:
                return None
            else:
                return _node(nums[mid],construct_tree(l,mid-1),construct_tree(mid+1,r))
        
        return construct_tree(0,len(nums)-1)
正文完
请博主喝杯咖啡吧!
post-qrcode
 
admin
版权声明:本站原创文章,由 admin 2019-03-26发表,共计865字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
验证码