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

思路一：在数据结构中，我们曾经学到过这样一个东西：二分搜索树（不是BST），这个树是根据二分搜索的搜索顺序而画出来的树。这棵树的特点就是它是绝对平衡的，并且是有序的。既然我们可以根据二分搜索的顺序来构建平衡二叉搜索树，那么我们就可以将原数组排成二分搜索此数组的顺序，这里用了集合容器作为额外空间存储。至于二分搜索的顺序模拟，是根据分冶来的。

然后就是树的构建，是数据结构的基础。注意:我们在写树的创建函数时，一定要返回一个值，因为我们的结点在创建以后并不会归到树中，需要我们人为的赋给这个空指针结点才行，不然会不存在。

这一种思路写起来其实挺麻烦的，但是思路很清晰。另外就是因为作者认为，这棵树需要实时是平衡二叉树才行，刚开始还把思路向着旋转那里去想了，结果手写特别麻烦，就没有采用那种思路。后来发现只要构建的树最后是平衡的就行，而不需要在创建的时候就一步一步都得是平衡树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer>list=new ArrayList<>();
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length<=0)
        return null;
        finds(nums);
        TreeNode root=new TreeNode(nums[nums.length/2],null,null);
        if(nums.length!=2){        
        for(int i=1;i<list.size();i++){
            create(root,list.get(i));
        }
        return root;
        }
        else{
            for(int i=0;i<list.size();i++){
            create(root,list.get(i));
        }
        return root;
        }
    }
    public void finds(int []nums){
        if(nums.length<=0)
        return;
        if(nums.length==1){
            list.add(nums[0]);
            return;
        }
        if(nums.length==2){
            list.add(nums[0]);
            list.add(nums[1]);
            return;
        }
        list.add(nums[nums.length/2]);
            int []left=new int[nums.length/2];
            int []right=new int[nums.length-nums.length/2-1];
            for(int i=0;i<nums.length/2;i++){
                left[i]=nums[i];
            }
            int k=0;
            for(int i=nums.length/2+1;i<nums.length;i++){
                right[k++]=nums[i];
            }
            finds(left);
            finds(right);
    }
    public TreeNode create(TreeNode root,int val){
        if(root==null){
            TreeNode tmp=new TreeNode(val,null,null);
            return tmp;
        }
        if(root.val>val){
            root.left=create(root.left,val);
        }
        else if(root.val<val){
            root.right=create(root.right,val);
        }
        return root;
    }
}

思路二：因为二叉搜索树的中序遍历正是一个升序的序列，所以我们可以任取一个结点，它的左边就是左子树，右边就是右子树。但又因为需要平衡，所以我们选择中间结点作为根，这样可以保证左右结点平衡，可以通过分冶递归实现。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return fenye(nums,0,nums.length-1);
    }
    public TreeNode fenye(int []nums,int l,int r){
        if(l>r)return null;
        int mid=l+(r-l)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=fenye(nums,l,mid-1);
        root.right=fenye(nums,mid+1,r);
        return root;
    }
}