109. 有序鏈表轉(zhuǎn)換二叉搜索樹

給定一個(gè)單鏈表，其中的元素按升序排序，將其轉(zhuǎn)換為高度平衡的二叉搜索樹。
本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過 1。
示例:
給定的有序鏈表： [-10, -3, 0, 5, 9],
一個(gè)可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個(gè)高度平衡二叉搜索樹：
0
/
-3 9
/ /
-10 5

思路

二叉搜索（查找）樹定義：
（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
（3）左、右子樹也分別為二叉排序樹；
（4）沒有鍵值相等的結(jié)點(diǎn)。

1 使用快慢指針法，找到鏈表的中間節(jié)點(diǎn)，該節(jié)點(diǎn)即為二叉查找樹的根節(jié)點(diǎn)
2 將根節(jié)點(diǎn)與前面鏈表斷開，再遞歸前后兩個(gè)鏈表，遞歸方法最終返回根節(jié)點(diǎn)

代碼

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null){
            return new TreeNode(head.val);
        }
        //pre節(jié)點(diǎn)指向slow的前節(jié)點(diǎn)
        ListNode pre = new ListNode(0, head);
        ListNode slow = head;
        ListNode fast = head;
        //fast走兩步，slow走一步，當(dāng)fast走完，slow則是中間節(jié)點(diǎn)，即為root
        while (fast != null && fast.next != null){
            pre = pre.next;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}