题目描述

给定一个有序数组，将它转换成一棵平衡二叉树。

对于这道题目，我们定义一棵平衡二叉树需要满足：任意节点的左右两棵子树的高度差不能大于1。

样例

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

一个合法方案是：[0,-3,9,-10,null,5]，如下所示：

      0
     / \
   -3   9
   /   /
 -10  5

算法

(递归) $O(n)$

递归建立整棵二叉树。
每次以中点为根，以左半部分为左子树，右半部分为右子树。先分别递归建立左子树和右子树，然后令根节点的指针分别指向两棵子树。

证明：
我们证明一个更强的结论，该算法得到的BST满足：任意节点的左右子树的所有高度的差不大于1（注意不是最大高度）。
在每一次递归过程中，左半部分的长度最多比右半部分的长度少1，那会不会有这种情况：左半部分的高度分别有 $m - 1, m$，右半部分的高度有 $m, m + 1$，则当前节点的高度就是 $m, m + 1, m + 2$（要加上当前根节点这一层，所以都要加1），则此时树的高度差为2，不平衡。
实际上这种情况是不可能的：反证，对于左子树，由于存在高度 $m - 1$，所以左半部分最多有 $2^m-2$ 个数；对于右子树，由于存在高度 $m$ 和 $m + 1$，所以右半部分最少有 $2^{m}$ 个数，此时左右两部分的数的个数最少差2，矛盾。

时间复杂度分析：一共建立 $n$ 个节点，在递归函数中，建立每个节点的复杂度是 $O(1)$，所以总时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(0, nums.size() - 1, nums);
    }

    TreeNode *build(int l, int r, vector<int>&nums)
    {
        if (l > r) return 0;
        int mid = (l + r) / 2;
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = build(l, mid - 1, nums);
        root->right = build(mid + 1, r, nums);
        return root;
    }
};