通过有序线性结构构造AVL树

本博客旨在结局利用有序数组和有序链表构造平衡二叉树（下文使用AVL树代指）问题。

直接通过旋转来构造AVL树似乎是一个不错的选择，但是稍加分析就会发现，这样平白无故做了许多毫无意义的旋转。因为直接通过旋转调整二叉查找树（下文使用BST代指）并没有利用数组或链表本身是有序的信息，进行了大量无意义的操作。

下面通过leetcode两道例题来说明这个问题。

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

题目分析

重点的问题在于：如何利用数组的有序信息呢？

首先我们先来观察一个有序数组和一棵AVL树所呈现的关系

 

 

我们可以发现数组中间元素恰好是对应AVL树的root节点（若数组长为偶数，可取中间偏左或偏右元，此时左右子树高度差为1）

我们只需要选取中间元素，构造头节点，在递归地构造其左右子树即可。

代码实现与说明

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return bui