题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

样例

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

算法分析

递归建立二叉搜索树，每次以中点为根结点，将左区间继续递归构建左子树，右区间继续递归构建右子树

证明：
假设枚举到当前点有n个结点，那么通过上面操作的方式，得到的左右子树对应的结构一定是固定的，等价于左右子树对应的高度也是固定的，用1个点作为根结点，剩余的n - 1个结点平均分配给左右子树继续递归

• 当n == 1时，建立二叉搜索树成立
• 当n == 2时，左子树为空，右子树1个，建立二叉搜索树成功
• 当n >= 3时，
  • (1)、 当n是奇数，根结点1个，剩余的n - 1个对左右子树分配，左子树的高度是$\lceil log_2{\frac{n - 1}{2}} \rceil$，右子树的高度也是$\lceil log_2{\frac{n - 1}{2}} \rceil$，两边子树的高度差是0，满足要求
  • (2)、 当n是偶数时，根结点1个，剩余的n - 1个对左右子树分配，左子树的高度是$\lceil log_2{\frac{n - 1}{2}} \rceil$，右子树的高度是$\lceil log_2{(\frac{n - 1}{2} + 1)} \rceil$，即$\lceil log_2{(\frac{n + 1}{2})} \rceil$，即证明$\lceil log_2{\frac{n + 1}{2}} \rceil - \lceil log_2{\frac{n - 1}{2}} \rceil <= 1$
  • 化简可得$\lceil log_2{(n + 1) - log_22} \rceil - \lceil log_2{(n - 1) - log_22} \rceil <= 1$
  • 即$\lceil log_2{(n + 1)} \rceil - \lceil log_2{(n - 1)} \rceil <= 1$
  • 只需满足$log_2(n + 1) - log_2(n - 1) > 1$不成立即可，等价于$log_2(n + 1) - log_2(n - 1) <= 1$
  • 即$log_2\frac{n + 1}{n - 1} <= 1$
  • 即$log_2(1 + \frac{2}{n - 1}) <= 1$，由于n >= 3
  • 因此$log_2(1 + \frac{2}{n - 1}) < log_2(1 + 1) == 1 $成立

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static TreeNode build(int[] nums, int l, int r)
    {
        if(l > r) return null;
        int k = (l + r) / 2;
        TreeNode root = new TreeNode(nums[k]);
        root.left = build(nums, l, k - 1);
        root.right = build(nums, k + 1, r);
        return root;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        int n = nums.length;
        return build(nums,0,n - 1);
    }
}