题解 | #将升序数组转化为平衡二叉搜索树#

题目：将升序数组转化为平衡二叉搜索树

描述：给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.

示例1：输入：[-1,0,1,2]，返回值：{1,0,2,-1}

解法一：

思路分析：二叉搜索树，又称之为二叉排序树（二叉查找树），它是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别是二叉搜索树。

平衡二叉搜索树为：保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均查找长度。该树的性质是：左子树与右子树高度之差的绝对值不超过1，树的每一个节点都有一个平衡因子，任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）

本题给出的是升序序列的有序数组，故可以保证数组是二叉搜索树中的中序遍历，我们首先应该确定二叉搜索树的根节点，然后其余数字分别位于平衡二叉树的左子树和右子树之中，当然左右子树也必须满足AVL，故可以通过递归的方式创建AVL树。

实例分析：[-1,0,1,2]，设置左右值，l和r，取中间变量为m，方便进行判断。

具体java代码如下所示：

import java.util.*;
 
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param num int整型一维数组
     * @return TreeNode类
     */
    TreeNode convert(int num[], int l, int r) {
        if (l >= r)
            return null;
        int m = (l + r) / 2;//平均分配
        TreeNode left = convert(num, l, m);//判断左子树为……
        TreeNode root = new TreeNode(num[m]);//确定根节点
        TreeNode right = convert(num, m + 1, r);
        root.left = left;
        root.right = right;
        return root;
    }
    public TreeNode sortedArrayToBST(int[] num) {
        return convert(num, 0, num.length);
    }
}

因为要递归遍历两层，第一层为确定根结点，第二层为判断是否符合条件，所以，其时间复杂度为O(N)，空间复杂度为O(1)。

解法二：

思路分析：为了降低时间，我们可以将数组从中点分成左右两份，用左侧的数字构建左子树，右侧的数字构建右子树，递归执行，直到数组长度为0。则可以保证树中任意节点的左子树高度和右子树高度最多相差1。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param num int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] num) {
        // write code here
        if(num == null || num.length == 0){
            return null;
        }
        int n = num.length;
        int mid = n/2;
        TreeNode node = new TreeNode(num[mid]);//将从中点开始进行判断
        int []numLeft = new int [mid];//中点左边为左子树
        int []numRight = new int [n-mid-1];//中点右边为右子树
        for(int i = 0 ; i<mid ; i++){//将左边的元素放进去
            numLeft[i] = num[i];
        }
        for(int i = mid+1 ; i<n ; i++){//将右边的元素放进去
            numRight[i-mid-1] = num[i];
        }
        node.left = sortedArrayToBST(numLeft);//循环遍历
        node.right = sortedArrayToBST(numRight);
        return node;
    }
}

因为要分别构建左右子树，并且需要循环判断左右子树的高度差值，所以时间复杂度为O(N)，空间复杂度为O(N)。