题目描述
给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）
方法一： 递归
解题思路
先了解一下平衡二叉搜索树的特点。
二叉搜索树，它的中序遍历后的结果就是一个升序的序列；
平衡的，说明任何一个节点的左子树和右子树的高度相差不超过1。
题目中所给的是一个升序排序的数组，所以一个大体流程就是根据一个中序遍历的序列，还原出一个它对应的二叉树。因为是中序遍历的结果，所以元素的左边都是以该元素为根节点的左子树上的元素，元素的右边都是以该元素为根节点的右子树上的元素。
又因为是平衡的，所以先找出序列的中点，以中点的值生成根节点，他的左边右边相差不差过一个元素，即它的左子树和右子树的元素个数相差不超过一个，每次都安一样的策略来找根节点，即左右子树的高度相差不会超过1。
以中点的左边序列为一个新的序列，按照一样的方法生成一个平衡二叉树，该树是第一步找的根节点的左子树。
以中点的右边序列为一个新的序列，按照一样的方法生成一个平衡二叉树，该树是第一步找的根节点的右子树。
也就是把问题的规模拆分成一个一个的小规模问题，解法都是一样的，只是问题的规模不一样，到规模足够小的时候我们可以很方便的找出答案，再一步一步往上推回去，即可得到真个大规模问题的答案。
在该题中，规模小到序列中只有一个元素时，即可很方便的找出答案，只有一个元素，直接以它为根节点返回即可。
以下以 [5，8，10，12，17] 数组为例，整个的递归的流程演示如下图所示：
复杂度分析
对于递归解决的问题，他的时间复杂度可以用 Master 公式来求解，虽然 Master 公式有它的适用条件，即大规模的问题每次拆分成的小问题规模都是一样的。该题符合这个条件，该题中每次拆分的小问题规模就是大问题规模的一半。
Master 公式：
说明：
T(n)： 表示样本量为 n 时的时间复杂度。
T(n / b) : 拆分的小问题规模，拆分成 b 等份。
a ： 小问题规模总共需要算几次。
O(n^d) : 除小问题规模的开销外，其他操作的时间复杂度。
由a、b、d的值，来决定对应的时间复杂度为多少：
- 1) log(b,a) > d ， 复杂度为O(N^log(b,a))
- 2) log(b,a) = d ， 复杂度为O(N^d * logN)
- 3) log(b,a) < d ， 复杂度为O(N^d)
在该题中，就是：T(n) = 2 * T(n/2) + O(1)，a=2，b=2，d=0；满足 log(2, 2) > 0，
所以时间复杂度为：O(N^log(2,2)) = O(N)
空间复杂度：O(N)
空间上的消耗有一部分是在栈的开辟上。在这个流程中，每次都将问题规模缩小了一半，所以栈上存储的数量也就是 logN 这么大。
另一部分是建立整个树需要 N 个节点，所以空间复杂度为O(N)。
示例代码
public class Solution {
/**
*
* @param num int整型一维数组
* @return TreeNode类
*/
public TreeNode sortedArrayToBST (int[] nums) {
// 判断特殊情况， 数组为空，或数组上没有元素，直接返回 null
if (nums == null || nums.length == 0) {
return null;
}
return process(nums, 0, nums.length - 1);
}
/**
*
* @param nums 整个的有序数组
* @param left 数组的左边界， 闭区间
* @param right 数组的右边界， 闭区间
* @return nums[left ... right] 这个范围的数组，转成 BST 后的根节点
*/
public TreeNode process(int[] nums, int left, int right) {
// 左边界 比 右边界 大， 说明数组上没有元素，直接返回 null
if (left > right) {
return null;
}
// 如果只有一个元素，就把它当成根节点直接返回
if (left == right) {
TreeNode root = new TreeNode(nums[left]);
return root;
}
// nums[left ... right] 这个数组的长度
int len = right - left + 1;
// nums[left ... right] 这个数组的中点下标，这个下标里的元素值就是 BST 的根节点的值
int mid = left + len / 2;
TreeNode root = new TreeNode(nums[mid]);
// 找出根节点的左子树： 继续递归用这个方法，找出左子树上这个局部范围的BST的根节点
root.left = process(nums, left, mid - 1);
// 找出根节点的右子树： 继续递归用这个方法，找出右子树上这个局部范围的BST的根节点
root.right = process(nums, mid + 1, right);
return root;
}
} 方法二： 用栈模拟递归
解题思路
之前说的是递归方法求解，但递归方法基本都可以改写成非递归方法，只是压栈出栈的行为我们自己操作了而已。
为了便于在栈中的操作，我们每次压栈的时候都需要记录保存一些信息，就该题来说，就要知道中点的值，以及这个中点对应范围的左边界和右边界。所以这里就自定义了一个 Node 类。
整个流程就是每次在栈里面压入根节点，然后找出这个根节点的左子树，当左边没有元素了，就再来生成右子树。生成右子树时的根节点的信息就从栈里面拿到（之前压入栈的作用就在这里）。
以下以 [5，8，10，12，17] 数组为例，整个的递归的流程演示如下图所示：
复杂度分析
时间复杂度： O(N^2)
看代码的书写有 2 个嵌套的 while 循环，所以时间复杂度即为 O(N^2)
空间复杂度：O(N)
空间的有一部分在 栈空间的存储上， 极端情况下把根节点的 “左节点” 全部存进去，个数就是这颗二叉树的高度，在生成右节点的时候会把之前存储的左节点弹出来在进行操作。
另一部分是建立整个树需要 N 个节点，所以空间复杂度为O(N)。
示例代码
public class Solution {
// 自定义的 Node 类， 保存压栈出栈需要用的信息
class Node {
TreeNode node; // 在 nums[left...right] 范围里，选出的根节点
int left; // 数组的左边界
int right; // 数组的右边界
public Node(TreeNode node, int left, int right) {
this.node = node;
this.left = left;
this.right = right;
}
}
/**
*
* @param nums int整型一维数组
* @return TreeNode类
*/
public TreeNode sortedArrayToBST (int[] nums) {
// 判断特殊情况， 数组为空，或数组上没有元素，直接返回 null
if (nums == null || nums.length == 0) {
return null;
}
// 左边界，闭区间
int left = 0;
// 右边界，闭区间
int right = nums.length - 1;
// 左右边界范围里的中点，就是根节点上的值
int mid = left + (right - left + 1) / 2;
TreeNode root = new TreeNode(nums[mid]);
Stack<Node> stack = new Stack<>();
stack.push(new Node(root, left, right));
TreeNode curRoot = root;
// 还在范围里，或 栈里有元素，就继续操作
while (left < right || !stack.isEmpty()) {
// 生成左子树
// left == right ， 就只有一个元素，已经生成根节点了
while (left < right) {
// 右边界： 在 根节点的下标 的左边
right = mid - 1;
// 更新中点（寻找左子树上的根节点）
mid = left + (right - left + 1) / 2;
TreeNode leftNode = new TreeNode(nums[mid]);
curRoot.left = leftNode;
// 更新根节点（在子树的视角来看的根节点）
curRoot = curRoot.left;
// 压栈，之后弹出这个元素时再用它来生成右子树
stack.push(new Node(leftNode, left, right));
}
// 生成右子树
// 拿出栈里之前保存的元素，生成它的右子树
Node node = stack.pop();
left = node.left;
right = node.right;
mid = left + (right - left + 1) / 2;
// 左边界： 在 根节点的下标 的右边
left = mid + 1;
// left <= right 说明右子树上还有元素，需要生成根节点
if (left <= right) {
// 更新中点（寻找右子树上的根节点）
mid = left + (right - left + 1) / 2;
curRoot = node.node;
TreeNode rightNode = new TreeNode(nums[mid]);
curRoot.right = rightNode;
// 更新根节点（在子树的视角来看的根节点）
curRoot = curRoot.right;
// 压栈， 这个节点也可能会有左节点或者右节点
stack.push(new Node(rightNode, left, right));
}
}
// 返回整颗树的根节点
return root;
}
} 
京公网安备 11010502036488号