108.将有序数组转换为二叉搜索树

• 将有序数组转换为二叉搜索树
• 思路：
  将数组转换为平衡树：每次取数组中间值构造根节点（对于偶数数组，不管取哪个都是平衡的，只是样子不同）；
  数组为有序：这样构造出来的树变成搜索树，而不是普通的二叉树

class Solution {
private:
    // 循环不变量[beg, end)
    TreeNode* tarvel(vector<int>& nums, int beg, int end) {
        if(beg == end) return NULL;

        int mid = beg + (end - beg) / 2; //等价于(beg + end) /2,但第二种写法可能会int溢出
        TreeNode* root = new TreeNode(nums[mid]);

        root->left = tarvel(nums, beg, mid);
        root->right = tarvel(nums, mid + 1, end);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return NULL;

        return tarvel(nums, 0, size);
    }
};

• 总结：

1. 数组转为二叉树，通常取数组中间值作为根结点，这样形成的就是平衡树
2. 若还是有序数组，则普通二叉树会升级为二叉搜索树
3. 取数组的中间值时,mid = beg + (end - beg) / 2更好，可以避免mid = (beg + end) / 2的加法溢出
4. 对于数组的递归，传递下标区间而不用每次构建一个新的子数组（注意保持循环不变量）
5. 循环不变量的区间和对应的判断条件是配套的