题目描述

高度平衡二叉搜索树。

样例

blablabla

算法1

中序遍历，总是选择中间位置左边的数字作为根节点 : mid=(left+right)/2
中序遍历，总是选择中间位置右边的数字作为根节点 : mid=(left+right+1)/2

时间复杂度

参考文献

C++ 代码

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

    TreeNode* buildtree(int l, int r, vector<int>& nums)
    {
        if(l > r) return 0;
        int mid = (l + r + 1)  >> 1; //// 这里要注意观察预期结果是选择中间位置的那一边
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = buildtree(l, mid - 1, nums);
        root->right = buildtree(mid + 1, r, nums);
        return root;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla