将有序数组转换为二叉搜索树（ LeetCode 108 ）
一、题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 将有序数组转换为二叉搜索树（ LeetCode 108 ）：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(nums,0,nums.length - 1);
}
// 将升序排序数组 nums，从下标 begin 到 end 的部分元素转换为平衡二叉排序树
private TreeNode toBST(int[] nums, int begin,int end){
// 整个递归的终止条件是 begin 的位置超过了 end
// 比如对于排序数组 [ 7，8 ]，它的起始位置 begin 为 0，结束位置 end 为 1
// 所以 mid 为 （ 0 + 1 ）/ 2 = 0
// 这个时候根据 mid 的位置划分为两个子区域
// [begin , mid - 1] 和 [ mid + 1 , end ]
// 即 7 的左区域位置为 [ 0 ，-1]，这个区域的 begin 为 0 ，end 为 -1
// 所以返回 null，结束了递归
// 很直观的可以看到对于排序数组 [ 7，8 ]来说，在数组中没有小于 7 的元素
if(begin > end) return null;
// 获取从 begin 到 end 排序数组中中间元素的下标
int mid = (begin + end) / 2 ;
// 获取以 mid 下标的元素
// 把这个元素作为转换后的二叉树根节点
TreeNode root = new TreeNode(nums[mid]);
// 递归的将 mid 左侧所有元素转换为平衡二叉排序树
TreeNode left = toBST(nums,begin,mid - 1);
// 递归的将 mid 右侧所有元素转换为平衡二叉排序树
TreeNode right = toBST(nums,mid + 1,end);
// 将 mid 左侧所有元素转换为平衡二叉排序树后作为 root 的左子树
root.left = left;
// 将 mid 右侧所有元素转换为平衡二叉排序树后作为 root 的右子树
root.right = right;
// 返回转换好的平衡二叉排序树
return root;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 将有序数组转换为二叉搜索树（ LeetCode 108 ）：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int> nums) {
return toBST(nums,0,nums.size() - 1);
}
// 将升序排序数组 nums，从下标 begin 到 end 的部分元素转换为平衡二叉排序树
TreeNode* toBST(vector<int>& nums, int begin, int end){
// 整个递归的终止条件是 begin 的位置超过了 end
// 比如对于排序数组 [ 7，8 ]，它的起始位置 begin 为 0，结束位置 end 为 1
// 所以 mid 为 （ 0 + 1 ）/ 2 = 0
// 这个时候根据 mid 的位置划分为两个子区域
// [begin , mid - 1] 和 [ mid + 1 , end ]
// 即 7 的左区域位置为 [ 0 ，-1]，这个区域的 begin 为 0 ，end 为 -1
// 所以返回 NULL，结束了递归
// 很直观的可以看到对于排序数组 [ 7，8 ]来说，在数组中没有小于 7 的元素
if(begin > end) return NULL;
// 获取从 begin 到 end 排序数组中中间元素的下标
int mid = (begin + end) / 2 ;
// 获取以 mid 下标的元素
// 把这个元素作为转换后的二叉树根节点
TreeNode* root = new TreeNode(nums[mid]);
// 递归的将 mid 左侧所有元素转换为平衡二叉排序树
TreeNode* left = toBST(nums,begin,mid - 1);
// 递归的将 mid 右侧所有元素转换为平衡二叉排序树
TreeNode* right = toBST(nums,mid + 1,end);
// 将 mid 左侧所有元素转换为平衡二叉排序树后作为 root 的左子树
root->left = left;
// 将 mid 右侧所有元素转换为平衡二叉排序树后作为 root 的右子树
root->right = right;
// 返回转换好的平衡二叉排序树
return root;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 将有序数组转换为二叉搜索树（ LeetCode 108 ）：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
return self.toBST(nums,0,len(nums) - 1)
# 将升序排序数组 nums，从下标 begin 到 end 的部分元素转换为平衡二叉排序树
def toBST(self,nums : List[int], begin : int , end : int ) -> TreeNode:
# 整个递归的终止条件是 begin 的位置超过了 end
# 比如对于排序数组 [ 7，8 ]，它的起始位置 begin 为 0，结束位置 end 为 1
# 所以 mid 为 （ 0 + 1 ）/ 2 = 0
# 这个时候根据 mid 的位置划分为两个子区域
# [begin , mid - 1] 和 [ mid + 1 , end ]
# 即 7 的左区域位置为 [ 0 ，-1]，这个区域的 begin 为 0 ，end 为 -1
# 所以返回 None，结束了递归
# 很直观的可以看到对于排序数组 [ 7，8 ]来说，在数组中没有小于 7 的元素
if begin > end :
return None
# 获取从 begin 到 end 排序数组中中间元素的下标
mid = (begin + end ) // 2
# 获取以 mid 下标的元素
# 把这个元素作为转换后的二叉树根节点
root = TreeNode(nums[mid])
# 递归的将 mid 左侧所有元素转换为平衡二叉排序树
left = self.toBST(nums,begin,mid - 1)
# 递归的将 mid 右侧所有元素转换为平衡二叉排序树
right = self.toBST(nums,mid + 1,end)
# 将 mid 左侧所有元素转换为平衡二叉排序树后作为 root 的左子树
root.left = left
# 将 mid 右侧所有元素转换为平衡二叉排序树后作为 root 的右子树
root.right = right
# 返回转换好的平衡二叉排序树
return root
