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

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

思路

与构造二叉树相似,我们需要找到中间节点,但是这是二叉搜索树,并且给定了一个升序数组,我们只需要找到升序数组中的中间节点便可以作为二叉树的中间节点。

递归得到左节点和右节点。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    TreeNode* traversal(vector<int>& nums,int left,int right) {
        //返回
        if(left == right) return nullptr;
        //取中间节点作为根节点  
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        //递归左右节点
        node->left = traversal(nums,left,mid);
        node->right = traversal(nums,mid+1,right);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums,0,nums.size());
        return root;
    }
};