109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / 
   -3   9
   /   /
 -10  5

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        if(list.size() == 0) return null;
        return help(list, 0, list.size() - 1);
    }
    public TreeNode help(List<Integer> list, int start, int end){
        if(start > end) return null;
        int rootind = (end + start) / 2;
        TreeNode root = new TreeNode(list.get(rootind));
        root.left = help(list, start, rootind - 1);
        root.right = help(list, rootind + 1, end);
        return root;
    }
}

一定是end+start/2，不是减。

既然linkedlist无法随机访问，就把它先转化成list或者array，就和108一样。

public TreeNode sortedListToBST(ListNode head) {
    return sortedArrayToBST(head, null);
}

private TreeNode sortedArrayToBST(ListNode head, ListNode tail) {
    if (head == tail) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != tail && fast.next != tail) {
        slow = slow.next;
        fast = fast.next.next;
    }

    TreeNode root = new TreeNode(slow.val);
    root.left = sortedArrayToBST(head, slow);
    root.right = sortedArrayToBST(slow.next, tail); 
    return root;
}

这个快慢指针做法也很有意思