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.

Solution:

1. 找到midNode，这个就是root node

2. 两边建树 分别加到这个root的left, right

注意左右字数可能为null的情况 以及midNode可能为head的情况

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode mid = findMiddle(head);
    TreeNode root = new TreeNode(mid.val);
    ListNode midPost = mid.next;
    if (mid != head) {
        root.left = sortedListToBST(head);
    }
    root.right = sortedListToBST(midPost);

    return root;

}

public ListNode findMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    ListNode pre = null;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    //Remember to set pre.next = null
    if (pre != null) {
        pre.next = null;
    }
    return slow;
}

Share