题目描述

给出一个升序排序的数组，将其转化为平衡二叉搜索树（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;
    } 
}