将有序数组转换为二叉搜索树

示例 1 $nums = [- 10, - 3, 0, 5, 9]$ ，我们从数组正中间的数 $nums [2] = 0$ 开始，把数组一分为二，得到两个小数组：

左： $[- 10, - 3]$ 。
右： $[5, 9]$ 。

答案由三部分组成：

根节点：节点值为 $nums [2] = 0$ 。
把 $nums [2]$ 左边的 $[- 10, - 3]$ 转换成一棵平衡二叉搜索树，作为答案的左儿子。这是一个和原问题相似的子问题，可以递归解决。
把 $nums [2]$ 右边的 $[5, 9]$ 转换成一棵平衡二叉搜索树，作为答案的右儿子。这是一个和原问题相似的子问题，可以递归解决。

递归边界：如果数组长度等于 $0$ ，返回空节点。

晕递归的同学，可以看视频讲解【基础算法精讲 09】，带你理解递归的本质。

⚠注意：答案可能不是唯一的。如果 $n$ 是偶数，我们可以取数组正中间左边那个数作为根节点的值，也可以取数组正中间右边那个数作为根节点的值。下面代码取的是正中间右边那个数，即下标为 $\frac{n}{2}$ 的数（当 $n$ 是偶数时）。

Python 解法1C++ 解法1

python

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        m = len(nums) // 2
        left = self.sortedArrayToBST(nums[:m])
        right = self.sortedArrayToBST(nums[m + 1:])
        return TreeNode(nums[m], left, right)

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 把 nums[left:right] 转成平衡二叉搜索树
        def dfs(left: int, right: int) -> Optional[TreeNode]:
            if left == right:
                return None
            m = (left + right) // 2
            return TreeNode(nums[m], dfs(left, m), dfs(m + 1, right))
        return dfs(0, len(nums))

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
    // 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
    TreeNode* dfs(vector<int>& nums, int left, int right) {
        if (left == right) {
            return nullptr;
        }
        int m = left + (right - left) / 2;
        return new TreeNode(nums[m], dfs(nums, left, m), dfs(nums, m + 1, right));
    }

public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums, 0, nums.size());
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。每次递归要么返回空节点，要么把 $nums$ 的一个数转成一个节点，所以递归次数是 $O (n)$ 的，所以时间复杂度是 $O (n)$ 。需要注意，Python 的第一种写法有切片的复制开销，二叉树的每一层都需要花费 $O (n)$ 的时间，一共有 $O (\log n)$ 层，所以时间复杂度是 $O (n \log n)$ ；第二种写法避免了切片的复制开销，时间复杂度是 $O (n)$ 。
空间复杂度： $O (n)$ 。如果不计入返回值和切片的空间，那么空间复杂度为 $O (\log n)$ ，即递归栈的开销。

更多相似题目，见下面的二叉树题单。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

分类题单 ​

复杂度分析

分类题单