leetcode-108：将有序数组转换为二叉搜索树

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def inorder(left,right):
            if left>right:
                return 
            mid = (left+right)//2
            root = TreeNode(nums[mid])
            root.left = inorder(left,mid-1)
            root.right = inorder(mid+1,right)
            return root
        return inorder(0,len(nums)-1)

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