Leetcode-109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

来源：力扣（LeetCode）

类似第108题，依然采用递归和二分法。

自己的方法，用了快慢指针来寻找链表的中点，并在中点的位置处截断链表。注意还需要用一个pre指针还记录中点位置(slow)的前驱节点。

class Solution { public TreeNode sortedListToBST(ListNode head) { return helper(head); } public TreeNode helper(ListNode head){ if(head==null) return null; if(head.next==null) return new TreeNode(head.val); ListNode fast=head; ListNode slow=head; ListNode pre=null; while(fast!=null&&fast.next!=null){ pre=slow; fast=fast.next.next; slow=slow.next; } pre.next=null; //截断 TreeNode node=new TreeNode(slow.val); node.left=helper(head); node.right=helper(slow.next); return node; } }

别人的方法(去掉了pre指针，而是又写了一个函数，把二分的两个端点作为传入的参数)

class Solution { public TreeNode sortedListToBST(ListNode head) { return helper(head,null); } public TreeNode helper(ListNode left,ListNode right){ if(left==right) return null; ListNode mid=getMid(left,right); TreeNode node=new TreeNode(mid.val); node.left=helper(left,mid); node.right=helper(mid.next,right); return node; } public ListNode getMid(ListNode left,ListNode right){ ListNode fast=left; ListNode slow=left; while(fast!=right&&fast.next!=right){ fast=fast.next.next; slow=slow.next; } return slow; } }