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

二叉搜索树（Binary Sort Tree）
二叉搜索树，又称之为二叉排序树（二叉查找树），它或许是一棵空树，或许是具有以下性质的二叉树：

若他的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别是二叉搜索树

二叉平衡搜索树（AVL）
前面提到了二叉搜索树，我们知道，二叉搜索树的特性便于我们进行查找插入删除等一系列操作，其时间复杂度为O（logn），但是，如果遇见最差的情况，比如以下这棵树：

这棵树，说是树，其实它已经退化成链表了，但从概念上来看，它仍是一棵二叉搜索树，只要我们按照逐次增大，如1、2、3、4、5、6的顺序构造一棵二叉搜索树，则形如上图。那么插入的时间复杂度就变成了O(n)，导致这种糟糕的情况原因是因为这棵树极其不平衡，右树的重量远大于左树，因此我们提出了叫平衡二叉搜索树的结构，又称之为AVL树，是因为平衡二叉搜索树的发明者为Adel’son-Vel’skii 和Landis二人。
平衡二叉搜索树，它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均查找长度。
AVL树的性质：
本质：仍是一棵二叉搜索树，只不过增加了平衡的要求

1. 若他的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3. 左子树与右子树高度之差的绝对值不超过1
4. 树的每个左子树和右子树都是AVL树
5. 每一个节点都有一个平衡因子（balance factor），任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）

将升序数组转化为平衡二叉搜索树
题解一：二分+递归
题解思路： 利用BST中序遍历为升序序列的特性。
BST中序遍历：
[1,2,3,4,5,6,7]转换为AVL二叉搜索树后为:

思路分析： 为了保持平衡，每次选择区间的中间值作为根节点。
递归分析：
递归边界： (left > right) 返回NULL；
递归过程： 选取中间值作为根节点，root = mid = (left+right+1)/2; 递归构建左右子树。

复杂度分析：
时间复杂度：O(N) 节点数N
空间复杂度：O(logN)

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) {

        if (num == null || num.length == 0) {
            return null;
        }

        return buildAvlTree(num, 0, num.length-1);
    }

    /**
     * 题目中所给的是一个升序排序的数组，所以一个大体流程就是根据一个中序遍历的序列，还原出一个它对应的二叉树。
     * 因为是中序遍历的结果，所以元素的左边都是以该元素为根节点的左子树上的元素，
     * 元素的右边都是以该元素为根节点的右子树上的元素。
     *
     * 又因为是平衡的，所以先找出序列的中点，以中点的值生成根节点，他的左边右边相差不差过一个元素，
     * 即它的左子树和右子树的元素个数相差不超过一个，每次都安一样的策略来找根节点，即左右子树的高度相差不会超过1。
     *
     * 以中点的左边序列为一个新的序列，按照一样的方法生成一个平衡二叉树，该树是第一步找的根节点的左子树。
     *
     * 以中点的右边序列为一个新的序列，按照一样的方法生成一个平衡二叉树，该树是第一步找的根节点的右子树。
     *
     * 也就是把问题的规模拆分成一个一个的小规模问题，解法都是一样的，只是问题的规模不一样，
     * 到规模足够小的时候我们可以很方便的找出答案，再一步一步往上推回去，即可得到真个大规模问题的答案。
     * 
     */
    public TreeNode buildAvlTree (int[] num, int start, int end) {

        if (start == end) {
            return new TreeNode(num[start]);
        }

        if (start > end) {
            return null;
        }

        //不能写成(start+end)/2,防止start+end越界超出int范围
        //是num的中位 所以要+1
        int mid = start + (end - start + 1)/2;

        TreeNode root = new TreeNode(num[mid]);
        root.left = buildAvlTree(num, start, mid-1);
        root.right = buildAvlTree(num, mid+1, end);

        return root;
    }
}