text: # 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)