通过有序线性结构构造AVL树
本博客旨在结局利用有序数组和有序链表构造平衡二叉树（下文使用AVL树代指）问题。
直接通过旋转来构造AVL树似乎是一个不错的选择，但是稍加分析就会发现，这样平白无故做了许多毫无意义的旋转。因为直接通过旋转调整二叉查找树（下文使用BST代指）并没有利用数组或链表本身是有序的信息，进行了大量无意义的操作。
下面通过leetcode两道例题来说明这个问题。
1. 108. 将有序数组转换为二叉搜索树
题目分析
重点的问题在于：如何利用数组的有序信息呢？
首先我们先来观察一个有序数组和一棵AVL树所呈现的关系
我们可以发现数组中间元素恰好是对应AVL树的root节点（若数组长为偶数，可取中间偏左或偏右元，此时左右子树高度差为1）
我们只需要选取中间元素，构造头节点，在递归地构造其左右子树即可。
代码实现与说明
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int l, int r) {
// 为什么采用l小于r而不是等于来判断呢？
// 我们这里是采用的闭区间的写法，当然可以采用闭开区间的写法，也就是等于时返回null
// 循环和递归函数的边界条件一定要多加注意
if (l > r)
return null;
// 防止因为l和r过大造成溢出，不过这道题数组长度不会那么大，但最好还是养成这样的习惯
int mid = l + (r - l) / 2;
// 其实这是一个中序遍历，先建立root节点，在递归地建立左子树和右子树
TreeNode node = new TreeNode(nums[mid]);
node.left = build(nums, l, mid - 1);
node.right = build(nums, mid + 1, r);
// 建立好后返回root节点即可
return node;
}
}
递归函数是如何设计的呢？
- 参数：我们需要访问nums数组元素，因此需要将其传入函数，也可以在Solution类中设计一个实例变量引用nums数组。同时，为例确定中间元素，我们需要明确数组的左右边界，因此传入参数l和r，它们也是判断数组内是否还有元素用来建立AVL树节点，也就是说当l小于r时，返回null节点。
- 返回值：这个比较显而易见，我们需要递归函数返回一个TreeNode节点（或者说它是已构造好子树的头节点）。
复杂度分析
时间复杂度：这道题本质上是使用先序遍历的方式构造一棵树，每个节点都被构造一次且路过三次，所以时间复杂度显然为O(N)
空间复杂度：递归调用栈深度为树的深度，由于构造的树为AVL树，其深度不超过lg(N)，递归调用栈深度也不超过O(lgN)，故空间复杂度为O(lgN)
2. 109. 有序链表转换二叉搜索树
题目分析
这道题是108题的兄弟版本，数组可以随机访问元素，因此我们可以轻而易举地得到中间元素，但是链表不再具备这个特性。因此我们需要采取其他的方法来解决这个问题。
- 将链表元素依次取出，构造出一个有序数组，再利用108的方法去做。不过空间复杂度提升为O(N)
- 采用快慢指针法取出中间节点，但是每次构造子树root节点均需使用快慢指针法，导致时间复杂度会降低为O(lgN)
- 更优秀的方法：利用AVL树中序遍历生成的序列即为所给有序链表这一性质，采用中序遍历构造AVL树，兼具方法1和方法2的优点
代码实现与说明
方法1不给出代码，其实相比于108题只是多了一步构造数组罢了。
方法2代码
class Solution {
public TreeNode sortedListToBST(ListNode head) {
return build(head, null);
}
private TreeNode build(ListNode l, ListNode r) {
if (l == r)
return null;
ListNode slow = l, fast = slow;
// 快慢指针寻找中间节点，可以说是本做法的核心，注意循环的条件
while (fast != r && fast.next != r) {
slow = slow.next;
fast = fast.next.next;
}
// 其实这是一个先序遍历的过程，在过程AVL树
TreeNode node = new TreeNode(slow.val);
node.left = build(l, slow);
node.right = build(slow.next, r);
return node;
}
}
递归函数设计说明:
- 返回值：返回值显然要返回树节点，因为我们需要向上一级调用函数返回构造好子树的头节点
- 参数：本函数参数选择是重中之重，向上面代码所示选用闭开区间的写法可以避免一些麻烦，不要忘记这是个单链表，如写成闭区间的模式，那么需要额外的prev指针来指示slow指针的前一个元素（对照108的代码去看)
方法2缺陷：快慢指针寻找中间元素所需时间复杂度是o(lgN)，我们每次在构造子树root节点时均需要使用它一次，这无疑造成了一些浪费。让我们回到108题所示图片中（把那个数组想象为一个链表），AVL树中序遍历产生的序列与链表是一致的。可以利用这个特点改进方法2吗？
方法3思路说明：
这里附上一份详细的参考链接
方法3代码
class Solution {
// 递归过程中各个函数均维护一个链表头，故将其设为实例变量
ListNode listHead;
public TreeNode sortedListToBST(ListNode head) {
listHead = head;
int length = getLength(head);
return build(0, length - 1);
}
// 一定要多注意该函数参数的设计，参数是整数索引！不再像方法2那样是ListNode引用
// 一定要好好理解这个函数
private TreeNode build(int left, int right) {
if (left > right)
return null;
TreeNode node = new TreeNode();
int mid = left + (right - left) / 2;
node.left = build(left, mid - 1);
node.val = listHead.val;
listHead = listHead.next;
node.right = build(mid + 1, right);
return node;
}
// 辅助函数，作用是遍历链表，统计其长度
private int getLength(ListNode head) {
int counter = 0;
while (head != null) {
counter++;
head = head.next;
}
return counter;
}
}
递归函数的说明：
- 参数设计：有些人（包括我在内）开始可能很诧异为什么不像方法2一样使ListNode作为参数呢？不要忘记，一旦参数使用ListNode那不就变成方法2了嘛，无法直接访问中间元素。要想直接访问中间元，就要使用整数索引。
- 如何理解递归函数的流程：最好的方法就是逐行分析代码，尝试模拟运行。不过这里还是给出一些说明，首先我们先建立node节点，先递归地建立其左子树，然后将链表头listHead指向下一个元素，此时listHead指向的节点恰好为中间节点，我们取出它的值，再递归地建立其右子树。
__EOF__
