LeetCode算法第109题：有序链表转换二叉搜索树

题目描述：

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

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

示例:

给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
 0
 / \
 -3 9
 / /
-10 5

思路：

这道题目和108题 将有序数组转换成二叉搜索树的思路一致，区别在于单链表不能直接定位中间元素。因此可以定义两个指针从单链表的头向尾进行遍历，一个指针每次向后移动一个元素，另一个指针每次向后移动两个元素。当移动较快的指针移动到单链表的尾部时，移动较慢的指针正好就在单链表的中间位置。然后将该单链表截取为前后两个链表，使用相同的思路将两个子链表分别生成左右子树。

Java代码：

public TreeNode sortedListToBST(ListNode head) {
 if(null == head){
 return null;
 }
 if(null == head.next){
 return new TreeNode(head.val);
 }
 //查找中位数
 ListNode slow = head;
 ListNode fast = head;
 ListNode tail = slow;
 while(null != fast && null != fast.next){
 tail = slow;
 slow = slow.next;
 fast = fast.next.next;
 }
 TreeNode root = new TreeNode(slow.val);
 //中位数之前的元素生成左子树
 tail.next = null;
 root.left = sortedListToBST(head);
 //中位数之后的元素生成右子树
 root.right = sortedListToBST(slow.next);
 return root;
 }
 

關鍵字: 单链表 ; 二叉