将有序数组转换为二叉搜索树( 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

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注