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;}
}