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

2,553次阅读

共计 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)

正文完

请博主喝杯咖啡吧！