108. 将有序数组转换为二叉搜索树 --力扣 --JAVA

简介: 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

 题目

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路

    1. 可以采用二分法,每次选数组中间值为根节点创建树,这样可以确保左右子树的高度差的绝对值不超过1;
    2. 通过递归来逐级生成后续节点;
    3. 可通过变量设置左右边界,方便后续节点区间的取值;

    代码展示

    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            TreeNode data = toBST(nums, 0, nums.length - 1);
            return data;
        }
        public TreeNode toBST(int[] nums, int left, int right){
            if(left > right){
                return null;
            }
            int middle = (left + right) / 2;
            return new TreeNode(nums[middle], toBST(nums, left, middle - 1), toBST(nums, middle + 1, right));
        }
    }

    image.gif


    目录
    相关文章
    |
    30天前
    leetCode(删除有序数组中的重复项)
    如何在不使用额外空间的情况下,通过双指针法原地删除有序数组中的重复项。
    32 2
    |
    3月前
    |
    存储 Java API
    LeetCode------合并两个有序数组(4)【数组】
    这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
    LeetCode------合并两个有序数组(4)【数组】
    |
    29天前
    【LeetCode 48】108.将有序数组转换为二叉搜索树
    【LeetCode 48】108.将有序数组转换为二叉搜索树
    34 0
    |
    3月前
    |
    算法
    LeetCode第26题删除有序数组中的重复项
    这篇文章介绍了LeetCode第26题"删除有序数组中的重复项"的解题方法,通过使用双指针技巧,高效地去除数组中的相邻重复元素。
    LeetCode第26题删除有序数组中的重复项
    |
    3月前
    |
    算法
    LeetCode第80题删除有序数组中的重复项 II
    文章介绍了LeetCode第80题"删除有序数组中的重复项 II"的解法,利用双指针技术在O(1)空间复杂度内原地删除重复元素,并总结了双指针技术在处理有序数组问题中的应用。
    LeetCode第80题删除有序数组中的重复项 II
    |
    3月前
    |
    算法
    LeetCode第88题合并两个有序数组
    文章分享了LeetCode第88题"合并两个有序数组"的解法,通过从后向前的合并策略避免了数组元素的前移,使用三个指针高效地完成了合并过程。
    |
    3月前
    |
    Python
    【Leetcode刷题Python】108. 将有序数组转换为二叉搜索树
    LeetCode上108号问题"将有序数组转换为二叉搜索树"的Python实现,通过递归选取数组中间值作为根节点,构建高度平衡的二叉搜索树。
    25 2
    |
    3月前
    |
    算法 Java
    LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
    LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
    54 0
    |
    3月前
    |
    Python
    【Leetcode刷题Python】26. 删除有序数组中的重复项
    本文提供了一种使用快慢指针法在原地删除升序数组中重复元素的Python实现,返回删除后数组的新长度,同时保持元素的相对顺序。
    43 0