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

2,329次阅读

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)