leetcode109题 有序链表转化成二叉搜索树

**第一种解题方式:**提绳子

太妙了哇!

思路分析:

1. 将链表里面的数据取出来,存储到数组里面 ,在重新创建一个链表

class Solution {public TreeNode sortedListToBST(ListNode head) {//首先对传入的参数进行一个判定if (head == null) {return null;}if (head.next == null) {return new TreeNode(head.val);}//递归提绳子,我觉得还是很好理解的ArrayList<Integer> list = new ArrayList<>();//开始保存节点while (head != null) {list.add(head.val);head = head.next;}
//        建立一颗这样的二叉树return  buildTreee(0,list.size() - 1,list);}//创造一个建立二叉树的方法public TreeNode buildTreee(int left,int right, List<Integer> list) {//编写递归循环的判定条件if (left > right) {return  null;}//开始提升子  但是必须要知道怎么提  对奇数和偶数绳子的中间节点进行一个归纳int mid = left + (right - left + 1) / 2;//进行递归的创建TreeNode root = new TreeNode(list.get(mid));root.left = buildTreee(left,mid -1 ,list);root.right = buildTreee(mid + 1,right,list);return root;}
}

第二种解法:快慢指针

其实这个题思路很好理解,但是细节其实并不是很好处理

1. 刚开始我是那我昨天那个对链表进行有序的排序,分治算法进行玩的 就没有把最中间的值单独分开
2. 但是这是一个递归的重新赋值,本来就是有序的,还是没有预备指针指向slow 结果就会多出好几个节点
3. 这就是 没有 进行单一拆分的后果

class Solution {public TreeNode sortedListToBST(ListNode head) {//首先对传入的参数进行一个判定if (head == null) {return null;}if (head.next == null) {return new TreeNode(head.val);}//也就还是昨天的快慢指针,寻找链表的中点ListNode fast = head;ListNode slow = head;ListNode pre = head;while (fast != null && fast.next != null) {pre = slow;fast = fast.next.next;slow = slow.next;}//这个时候  把链表从中间开始断开就好了ListNode temp = slow.next;pre.next = null;//递归往链表里面进行叠加就好了TreeNode root = new TreeNode(slow.val);root.left = sortedListToBST(head);root.right = sortedListToBST(temp);return root;}
}