深度优先搜索：力扣108. 将有序数组转换为二叉搜索树

1、题目描述：

2、题解：

可以和下面两道题一起做： 深度优先搜索、快慢指针：力扣109. 有序链表转换二叉搜索树 二叉搜索树：力扣1382. 将二叉搜索树变平衡 深度优先搜索 我们利用框架数据结构和算法 从0到1 ：二叉树和二叉搜索树。二叉搜索树的中序遍历是有序的。由于数组是有序的，我们可以把中间的值当成根结点，左、右的值分别为左、右子树。其实，相当于中序遍历 思路：

递归出口为：当数组为空时，返回 对于中间的值mid，创建TreeNode（mid），也即root = TreeNode（mid) 然后处理左子树 然后处理右子树 返回root # 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: #中序遍历 if not nums: return mid_index = len(nums) // 2 mid = nums[mid_index] root = TreeNode(mid) root.left = self.sortedArrayToBST(nums[:mid_index]) root.right = self.sortedArrayToBST(nums[mid_index + 1:]) return root

3、复杂度分析：

时间复杂度：O(N)，N是数组的长度，每个数字仅被访问一次 空间复杂度：O(logN)