• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

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

leetcode admin 6个月前 (03-26) 301次浏览 0个评论 扫描二维码
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)

Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Convert Sorted Array to Binary Search Tree(有序列表转化为 BST)
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!