将有序数组转换为二叉搜索树

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

初步分析

看到平衡二叉树，首先就想到了二分法。因为数组是个已经排序好的数组，所以用二分法，以中间的数为根节点，左边的为左子树，右边的为右子树，由此搭建出来的数必是平衡二叉树。

答案

public TreeNode sortedArrayToBST(int[] nums) {
        int first =0;
        int end = nums.length-1;
        return arrayToBST(first,end,nums);
    }
    public static TreeNode arrayToBST(int first,int end,int[]nums) {
        if(first>end){
            return null;
        }
        TreeNode treeNode = new TreeNode();
        int model = (first+end)/2;;
        treeNode.val = nums[model];
        treeNode.left = arrayToBST(first,model-1,nums);
        treeNode.right = arrayToBST(model+1,end,nums);
        return treeNode;
    }

复杂度

• 时间复杂度: O(n)，需要遍历完整个数组。
• 空间复杂度：O(logn)。因为用到递归，所以空间复杂度还是主要取决于递归占用的栈空间。

总结

平衡二叉树有两种情况，比如nums = [-10,-3,0,5,9]

都是这个题的答案，按照答案中的代码，实现出来的平衡二叉树就是第二种二叉树，那么怎么修改代码使其变成第一种平衡二叉树呢？

我们从代码可以看到，转折点就在于model。我们现在数组的长度为偶数的时候，将小的作为根节点，将大的做为此节点的右子树。那么我们只需要将这个条件进行处理就可以了。

public static TreeNode sortedArrayToBST(int[] nums) {
    int first =0;
    int end = nums.length-1;
    return arrayToBST(first,end,nums);
}
public static TreeNode arrayToBST(int first,int end,int[]nums) {
    if(first>end){
        return null;
    }
    TreeNode treeNode = new TreeNode();
    int model = (first+end)/2;
    if((first+end)%2!=0){
        treeNode.val = nums[model+1];
        treeNode.left = arrayToBST(first,model,nums);
        treeNode.right = arrayToBST(model+2,end,nums);
        return treeNode;
    }
    treeNode.val = nums[model];
    treeNode.left = arrayToBST(first,model-1,nums);
    treeNode.right = arrayToBST(model+1,end,nums);
    return treeNode;
}

处理完之后，如果这个数组长度如果是偶数，则将大的数作为根节点，将前边的小数作为左子树。

这两种解法都是正确答案。这个条件还是可以进行优化的。比如我们nums = [-10,-3,0,5,9]数组长度是5。

model =（0+4）/2 = 2,那么采用第二种计算方法mode =（0+4+1）/2=2。也就是当数组长度为偶数的时候，中间值不影响。

但是下一次比较数组为[-10,-3],model = (0+1)/2 =0,那么采用第二种计算方法mode =（0+1+1）/2=1。当数组长度为基数的时候，中间值却不一样。

所以将

int model = (first+end)/2;
    if((first+end)%2!=0){
        treeNode.val = nums[model+1];
        treeNode.left = arrayToBST(first,model,nums);
        treeNode.right = arrayToBST(model+2,end,nums);
        return treeNode;
    }

改为int model = (first+end)/2;即可实现。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！