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

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

思路：mid = (left + right) / 2 选中间元素作为根节点；

左子数组递归生成左子树；

右子数组递归生成右子树；

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }

private:
    TreeNode* build(const vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;  // 递归终止条件
        int mid = left + (right - left) / 2;  // 取中点
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = build(nums, left, mid - 1);
        root->right = build(nums, mid + 1, right);
        return root;
    }
};

思路：将数组折半建树

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums, 0, nums.size());
    }

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