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


    目录
    相关文章
    |
    3月前
    leetCode(删除有序数组中的重复项)
    如何在不使用额外空间的情况下,通过双指针法原地删除有序数组中的重复项。
    39 2
    |
    3月前
    【LeetCode 45】701.二叉搜索树中的插入操作
    【LeetCode 45】701.二叉搜索树中的插入操作
    16 1
    |
    3月前
    【LeetCode 44】235.二叉搜索树的最近公共祖先
    【LeetCode 44】235.二叉搜索树的最近公共祖先
    20 1
    |
    3月前
    【LeetCode 48】108.将有序数组转换为二叉搜索树
    【LeetCode 48】108.将有序数组转换为二叉搜索树
    46 0
    |
    3月前
    【LeetCode 47】669.修剪二叉搜索树
    【LeetCode 47】669.修剪二叉搜索树
    14 0
    |
    3月前
    【LeetCode 46】450.删除二叉搜索树的节点
    【LeetCode 46】450.删除二叉搜索树的节点
    24 0
    |
    3月前
    【LeetCode 42】501.二叉搜索树中的众数
    【LeetCode 42】501.二叉搜索树中的众数
    12 0
    |
    3月前
    【LeetCode 41】530.二叉搜索树的最小绝对差
    【LeetCode 41】530.二叉搜索树的最小绝对差
    15 0
    |
    3月前
    【LeetCode 40】98.验证二叉搜索树
    【LeetCode 40】98.验证二叉搜索树
    18 0
    |
    3月前
    【LeetCode 39】700.二叉搜索树中的搜索
    【LeetCode 39】700.二叉搜索树中的搜索
    22 0