将升序数组转化为平衡二叉搜索树

public TreeNode sortedArrayToBST (int[] nums) {
    // write code here
    if(nums==null || nums.length==0){
        return null;
    }
    int len=nums.length ,mid=len/2;
    TreeNode root=new TreeNode(nums[mid]);
    root.left=sortedArrayToBST(Arrays.copyOfRange(nums ,0 ,mid));
    root.right=sortedArrayToBST(Arrays.copyOfRange(nums ,mid+1 ,len));
    return root;
}

public class Solution22 {
	public TreeNode sortedArrayToBST(int[] num) {
        if(num==null||num.length==0)
        	return null;
        return sorted(num,0,num.length-1);
    }
    
    public TreeNode sorted(int[] num,int left,int right) {
    	 if(left>right)
    		 return null;
       	 int mid =(left+right+1)/2;
    	 int num1 =num[mid];
    	 TreeNode node = new TreeNode(num1);
    	 node.left =sorted(num,left,mid-1);
    	 node.right = sorted(num,mid+1,right);
    	 return node;
    }

}

import java.util.Arrays;
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num.length == 0)
            return null;
        if(num.length == 1)
            return new TreeNode(num[0]);
        if(num.length == 2)
        {
            TreeNode root = new TreeNode(num[1]);
            root.left = new TreeNode(num[0]);
            return root;
        }
        int length = num.length;
        int middle = length/2;
        TreeNode root = new TreeNode(num[middle]);
        int[] numLeft = Arrays.copyOfRange(num, 0, middle);
        int[] numRight = Arrays.copyOfRange(num, middle + 1, length);
        root.left = sortedArrayToBST(numLeft);
        root.right = sortedArrayToBST(numRight);
        return root;
    }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null)
            return null;
        return arrToBST(num, 0, num.length);
    }

    private TreeNode arrToBST(int[] num, int low, int high) {
        if (low < high && low < num.length) {
            int rootIndex = (low + high) / 2;
            TreeNode root = new TreeNode(num[rootIndex]);
            root.left = arrToBST(num, low, rootIndex);
            root.right = arrToBST(num, rootIndex+1, high);
            return root;
        }
        return null;
    }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        int len = num.length;
        return toBST(num,0,len);
    }
    
    public TreeNode toBST(int[] num,int start,int end){
        if(start == end) return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = toBST(num,start,mid);
        root.right = toBST(num,mid + 1,end);
        return root;
    }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0)
            return null;
        return sortedArrayToBST(num, 0, num.length - 1);
    }
    public TreeNode sortedArrayToBST(int[] num, int start, int end) {
        if (start > end)
            return null;
        if (start == end)
            return new TreeNode(num[start]);
        int mid = 0;
        if ((start + end) % 2 == 0) {
            mid = (start + end) / 2;
        } else {
            mid = (start + end) / 2 + 1;
        }
        TreeNode root = new TreeNode(num[mid]);
        TreeNode leftTree = null;
        TreeNode rightTree = null;
        if (mid - 1 >= 0 && mid >= start)
            leftTree = sortedArrayToBST(num, start, mid - 1);
        if (mid + 1 < num.length && mid + 1 <= end)
            rightTree = sortedArrayToBST(num, mid + 1, end);
        root.left = leftTree;
        root.right = rightTree;
        return root;
    }
}

/*递归思路：1.f(p,end)找到链表（起始p,到终止end）中最中间的节点，作为根节点,并返回。
           2.这个节点的left=f(p,中间节点)
           3.这个节点的right=f(中间节点.next，end)
*/      
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
       return  f(head,null);
    }
    public TreeNode f(ListNode p,ListNode end){
         if(p==null||p==end) return null;
         if(p.next==end) return new TreeNode(p.val);
        ListNode slow=p;
        ListNode fast=p;
        while(fast.next!=end && fast.next.next!=end){
            slow=slow.next;
            fast=fast.next.next;
        }
        if(fast.next!=end) //边界值处理
        slow=slow.next;
        TreeNode root  = new TreeNode(slow.val);
        root.left=f(p,slow);
        root.right=f(slow.next,end);
        return root;
    }
} 

	public TreeNode sortedArrayToBST(int[] num) { if (num.length == 0) { return null;
    }
    TreeNode head = helper(num, 0, num.length - 1); return head;
}

public TreeNode helper(int[] num, int low, int high) { if (low > high) { // Done return null;
    } int mid = (low + high) / 2;
    TreeNode node = new TreeNode(num[mid]);
    node.left = helper(num, low, mid - 1);
    node.right = helper(num, mid + 1, high); return node;
} 

public class Solution {
   public TreeNode sortedArrayToBST(int[] num) {
		if(num == null || num.length == 0) return null;
		return createTree(num, 0, num.length - 1);
	}
	public static TreeNode createTree(int[] num, int start, int end) {
		if(start > end) return null;
		int mid = (start + end) / 2 + (start + end) % 2;
		TreeNode root = new TreeNode(num[mid]);
		root.left = createTree(num, start, mid - 1);
		root.right = createTree(num, mid + 1, end);
		return root;
	}
}