题目地址(108. 将有序数组转换为二叉搜索树)
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
题目描述
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
前置知识
公司
思路
由于输入是一个升序排列的有序数组。因此任意选择一点，将其作为根节点，其左部分左节点，其右部分右节点即可。 因此我们很容易写出递归代码。
而题目要求是高度平衡的二叉搜索树，因此我们必须要取中点。 不难证明：由于是中点，因此左右两部分差不会大于 1，也就是说其形成的左右子树节点数最多相差 1，因此左右子树高度差的绝对值不超过 1。
形象一点来看就像你提起一根绳子，从中点提的话才能使得两边绳子长度相差最小。
关键点
代码
代码支持：JS，C++，Java，Python
JS Code:
var sortedArrayToBST = function (nums) {
// 由于数组是排序好的，因此一个思路就是将数组分成两半，一半是左子树，另一半是右子树
// 然后运用“树的递归性质”递归完成操作即可。
if (nums.length === 0) return null;
const mid = nums.length >> 1;
const root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
Python Code:
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return None
mid = (len(nums) - 1) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
复杂度分析
空间复杂度：每次递归都 copy 了 N 的 空间，因此空间复杂度为 $O(N ^ 2)$
然而，实际上没必要开辟新的空间：
C++ Code:
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return reBuild(nums, 0, nums.size()-1);
}
TreeNode* reBuild(vector<int>& nums, int left, int right)
{
// 终止条件：中序遍历为空
if(left > right)
{
return NULL;
}
// 建立当前子树的根节点
int mid = (left+right)/2;
TreeNode * root = new TreeNode(nums[mid]);
// 左子树的下层递归
root->left = reBuild(nums, left, mid-1);
// 右子树的下层递归
root->right = reBuild(nums, mid+1, right);
// 返回根节点
return root;
}
};
Java Code:
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length - 1);
}
private TreeNode dfs(int[] nums, int lo, int hi) {
if (lo > hi) {
return null;
}
int mid = lo + (hi - lo) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums, lo, mid - 1);
root.right = dfs(nums, mid + 1, hi);
return root;
}
}
Python Code:
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
return self.reBuild(nums, 0, len(nums)-1)
def reBuild(self, nums, left, right):
# 终止条件：
if left > right:
return
# 建立当前子树的根节点
mid = (left + right)//2
root = TreeNode(nums[mid])
# 左右子树的下层递归
root.left = self.reBuild(nums, left, mid-1)
root.right = self.reBuild(nums, mid+1, right)
return root
复杂度分析
空间复杂度：由于是平衡二叉树，因此隐式调用栈的开销为 $O(logN)$
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
公众号【 力扣加加】知乎专栏【 Lucifer - 知乎】
点关注，不迷路！
