LeetCode 109: Convert Sorted List to Binary Search Tree

/**
 * 109. Convert Sorted List to Binary Search Tree
 * 1. Time:O(nlogn)  Space:O(logn)
 * 2. Time:O(n)  Space:O(logn)
 */

// 1. Time:O(nlogn)  Space:O(logn)
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        ListNode mid = midNode(head);
        TreeNode root = new TreeNode(mid.val);
        if(head==mid)
            return root;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }
    
    private ListNode midNode(ListNode head){
        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        if(prev!=null)
            prev.next = null;
        return slow;
    }
}

// 2. Time:O(n)  Space:O(logn)
class Solution {
    
    private ListNode head;
    
    public TreeNode sortedListToBST(ListNode head) {
        int len = listLen(head);
        this.head = head;
        return helper(0,len-1);
    }
    
    private TreeNode helper(int start, int end){
        if(start>end) return null;
        int mid = (start+end) >>> 1;
        TreeNode left = helper(start,mid-1);
        TreeNode root = new TreeNode(this.head.val);
        root.left = left;
        this.head = this.head.next;
        TreeNode right = helper(mid+1,end);
        root.right = right;
        return root;
    }
    
    private int listLen(ListNode head){
        ListNode cur = head;
        int len = 0;
        while(cur!=null){
            cur = cur.next;
            len++;
        }
        return len;
    }
}

LeetCode 109: Convert Sorted List to Binary Search Tree

原文：https://www.cnblogs.com/AAAmsl/p/12842057.html