一.解法

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
要點(diǎn)：dfs深度優(yōu)先搜索，遞歸，樹
所給數(shù)組是二叉搜索樹的中序遍歷序列
選擇中間數(shù)字作為二叉搜索樹的根節(jié)點(diǎn)，這樣分給左右子樹的數(shù)字個(gè)數(shù)相同或只相差 1，可以使得樹保持平衡，創(chuàng)建的平衡二叉搜索樹根據(jù)邊界處理的不同不是唯一的
Python，C++，Java都用了相同的dfs方法，每次找中間元素，對中間元素的左孩子后右孩子進(jìn)行遞歸，邊界l，r分別修改為l，mid-1和mid+1，r

二.Python實(shí)現(xiàn)

# 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++實(shí)現(xiàn)

/**
 * 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實(shí)現(xiàn)

/**
 * 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;

    }
}