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

關鍵字: 高度 中位數 return