leetcode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree（使用c++/java/python）

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

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

递归。用二分法每次将有序数组的中间一个数作为根结点，其左边再用二分法构建左子树，其右边也用二分法构建右子树。

执行用时： c++ 12ms； java 1ms； python 80ms

c++

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = binarySearch(nums,0,nums.size()-1);
        return root;
    }
    
    TreeNode* binarySearch(vector<int>& nums, int low, int high)
    {
        if(low>high) return NULL;
        int mid = (low+high)/2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = binarySearch(nums,low,mid-1);
        node->right = binarySearch(nums,mid+1,high);
        return node;
    }
};

java

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = binarySearch(nums,0,nums.length-1);
        return root;
    }
    public TreeNode binarySearch(int[] nums, int lowidx, int highidx)
    {
        if(lowidx>highidx)  return null;
        int mididx = (lowidx+highidx)/2;
        TreeNode node = new TreeNode(nums[mididx]);
        node.left = binarySearch(nums,lowidx,mididx-1);
        node.right = binarySearch(nums,mididx+1,highidx);
        return node;
    }
}

python

class Solution:
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        root = self.binarySearch(nums,0,len(nums)-1)
        return root
        
    def binarySearch(self,nums,low,high):
        if low>high:
            return None
        mid = (low+high)//2
        node = TreeNode(nums[mid])
        node.left = self.binarySearch(nums,low,mid-1)
        node.right = self.binarySearch(nums,mid+1,high)
        return node