升序数组转化为平衡二叉搜索树

先序遍历。

注意一点即可，在求中点的过程中，理论上left + (right-left) / 2和left + (right - left + 1) / 2都是合法的，但从题目中的示例可以得知，我们的代码里应使用后者才能符合题意。

这有一个小插曲，刚开始我在sortedArrayToBST中写了如下代码，结果有5%的案例出现段错误，百思不得其姐，大家猜猜问题出在哪里？

TreeNode* sortedArrayToBST(vector<int>& num) {
    TreeNode *root;
    if (num.size() < 1) return root;
    root = preOrder(num, 0, num.size() - 1);
    return root;
}

完整正确代码如下：

class Solution {
public:
    /**
     *
     * @param num int整型vector
     * @return TreeNode类
     */
    TreeNode *sortedArrayToBST(vector<int> &num) {
        if (num.size() < 1) return nullptr;
        TreeNode *root = preOrder(num, 0, num.size() - 1);
        return root;
    }

    TreeNode *preOrder(vector<int> &num, int left, int right) {
        if (left > right) return nullptr;
        // 1. 找到中间节点
        int mid = left + (right - left + 1) / 2;
        // 2. 递归构建左右
        TreeNode *root = new TreeNode(num[mid]);
        root->left = preOrder(num, left, mid - 1);
        root->right = preOrder(num, mid + 1, right);
        return root;
    }
};