https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树（BST）。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
附：此题提交时必须注释掉class TreeNode类
法一：中序遍历，总是选择中间位置左边的数字作为根节点
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ def helper(left, right): if left > right: return None # 总是选择中间位置左边的数字作为根节点 mid = (left + right) // 2 root = TreeNode(nums[mid]) root.left = helper(left, mid - 1) root.right = helper(mid + 1, right) return root return helper(0, len(nums) - 1) # 写成helper返回时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。
空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-33/
二叉搜索树的中序遍历结果为递增序列。现在题目给了我们一个递增序列，要求我们构造一棵二叉搜索树，就是要实现这一特性的逆过程。
中序遍历的顺序为：左节点 → 根节点 → 右节点。
构造一棵树的过程可以拆分成无数个这样的子问题：构造树的每个节点以及节点之间的关系。对于每个节点来说，都需要：
选取节点构造该节点的左子树构造该节点的右子树要求构造一棵「高度平衡」的树，所以我们在选取节点时选择数组的中点作为根节点，以此来保证平衡性。
法一类似写法（没写helper函数）
# 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): if not nums: return None # 找到中点作为根节点 mid = len(nums) // 2 node = TreeNode(nums[mid]) # 左侧数组作为左子树 left = nums[:mid] right = nums[mid+1:] # 递归调用 node.left = self.sortedArrayToBST(left) node.right = self.sortedArrayToBST(right) return nodehttps://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/tu-jie-er-cha-sou-suo-shu-gou-zao-di-gui-python-go/
https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
与上一题108. 将有序数组转换为二叉搜索树，还是找中点，但是这个是链表找中点，用快慢指针。
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # 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 sortedListToBST(self, head: ListNode) -> TreeNode: def findmid(head, tail): slow = head fast = head while fast != tail and fast.next!= tail : slow = slow.next fast = fast.next.next return slow def helper(head, tail): if head == tail: return node = findmid(head, tail) root = TreeNode(node.val) root.left = helper(head, node) root.right = helper(node.next, tail) return root return helper(head, None)
