https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

题目

image.png

思路

image.png
https://leetcode-cn.com/problems/balance-a-binary-search-tree/solution/jiang-er-cha-sou-suo-shu-bian-ping-heng-by-leetcod/

代码

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
  10.         def helper(left, right):
  11.             if left > right:
  12.                 return None
  14.             # 总是选择中间位置左边的数字作为根节点
  15.             mid = (left + right) // 2
  17.             root = TreeNode(nums[mid])
  18.             root.left = helper(left, mid - 1)
  19.             root.right = helper(mid + 1, right)
  20.             return root
  22.         return helper(0, len(nums) - 1)