因为二叉搜索树中序遍历的结果就是一个从小到大排列的数组，因此数组的中间位置的值，就是二叉搜索树的根节点的值；
再依次采用递归，分别构建左右子树。
链表和数组的不同在于，数组可以直接索引找到元素，查找方便，链表不能够直接定位到某一个元素；所以要采用链表自己的方法，求中间位置；断开链表；进行迭代
链表解法的难点：
1.断开链表：采用双指针思路
2.查找链表中间节点位置的表达法
3.新建树节点值
class Solution { public TreeNode sortedArrayToBST(int[] nums) { /*数组是有序的，有序数组是二叉查找树中序遍历的结果，先找到根节点，在数组的中间位置； 在他的左边的值都比他小，属于左子树范围；在他的右节点的值都比他大，属于右子树范围； 要构建二叉搜索平衡树；则递归对左右子树分别构建平衡二叉搜索树*/ return MinBst(nums,0,nums.length-1); } public TreeNode MinBst(int[] nums,int start,int end){ if(start>end) return null; int mid=(start+end)/2; //有参构造函数 TreeNode root=new TreeNode(nums[mid]); root.left=MinBst(nums,start,mid-1); root.right=MinBst(nums,mid+1,end); return root; } } /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedListToBST(ListNode head) { /*链表和数组的不同在于，数组可以直接索引找到元素，方便查找 链表不能够直接定位到某一个元素；所以要采用链表自己的方法，求中间位置；断开链表；进行迭代*/ //1.判断边界条件 if(head==null)return null; if(head.next==null) return new TreeNode(head.val); //2.求出链表第一个链表的末尾/第二个链表的开头，中间链表节点的前一个节点 ListNode preMid=findPre(head); //3.求出中间节点 ListNode mid=preMid.next; //4.断开链表 preMid.next=null; //5.设置树的根节点 TreeNode root=new TreeNode(mid.val); //6.设置树的左子树和右子树 root.left=sortedListToBST(head); root.right=sortedListToBST(mid.next); return root; } public ListNode findPre(ListNode head){ ListNode slow=head; ListNode fast=head.next; ListNode pre=head; while(fast!=null&&fast.next!=null){ pre=slow; slow=slow.next; fast=fast.next.next; } return pre; } }
