leetc0de 108. 将有序数组转换为二叉搜索树
什么是“二叉搜索树 (BST)”？
二叉搜索树（Binary Search Tree）有一个绝对铁律：左小、右大。 对于树上的任何一个节点：
它的左子树里所有的值，都必须小于这个节点的值。
它的右子树里所有的值，都必须大于这个节点的值。
“平衡”的定义:一棵平衡二叉树规定，任何一个节点的左子树和右子树的深度（高度）差，绝对不能超过 1。
做题思路：如何把升序数组变成平衡二叉搜索树？
题目给的是一个已经排好序的数组，比如[-10, -3, 0, 5, 9]。 既然要保证“平衡”（左右两边节点数量差不多），又要保证“左小右大”，我们该选谁当这棵树的根节点？
答案呼之欲出：选最中间的那个数！
核心思路（分治法 / 递归）：
找中点当老大：取数组最中间的元素（比如这里的
0）作为根节点。这样，根节点左边的数全比它小，右边的数全比它大，且左右两边的数量绝对均等（或只差一个）。左半边建左子树：拿中点左边的数组段
[-10, -3]，继续重复第一步，把它的中点变成0的左孩子。右半边建右子树：拿中点右边的数组段
[5, 9]，继续重复第一步，把它的中点变成0的右孩子。何时结束：当切分出的数组段为空（没有元素了）时，说明到底了，返回空节点（
None）。
这个不断“找中间、分两头”的过程，其实就相当于把你平时查字典时用的二分查找法，实体化成了一棵看得见摸得着的树！
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: if not nums: return None length = len(nums)//2 left_tree = self.sortedArrayToBST(nums[0:length]) right_tree = self.sortedArrayToBST(nums[length+1:]) root = TreeNode(nums[length],left_tree,right_tree) return root