一.解法

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
要点：dfs深度优先搜索，递归，树
所给数组是二叉搜索树的中序遍历序列
选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡，创建的平衡二叉搜索树根据边界处理的不同不是唯一的
Python，C++，Java都用了相同的dfs方法，每次找中间元素，对中间元素的左孩子后右孩子进行递归，边界l，r分别修改为l，mid-1和mid+1，r

二.Python实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        return self.sortedArrayToBST2(nums,0,len(nums)-1)
    def sortedArrayToBST2(self, nums: List[int],l:int,r:int) -> TreeNode:
        if r<l:
            return None
        mid=int(l+(r-l)/2)
        root=TreeNode(nums[mid])
        root.left=self.sortedArrayToBST2(nums,l,mid-1)
        root.right=self.sortedArrayToBST2(nums,mid+1,r)
        return root

三.C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums, 0, nums.size() - 1);
    }
    TreeNode* sortedArrayToBST(vector<int>& nums, int l, int r) {
        if (r < l) return NULL;
        int mid = l + (r-l)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sortedArrayToBST(nums, l, mid - 1);
        root->right = sortedArrayToBST(nums, mid + 1, r);
        return root;
    }
};

四.java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums,0,nums.length-1);

    }

    TreeNode sortedArrayToBST(int[] nums,int l,int r){
        if(r<l) return null;
        int mid=l+(r-l)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=sortedArrayToBST(nums,l,mid-1);
        root.right=sortedArrayToBST(nums,mid+1,r);

        return root;

    }
}