LC 0109 [M] Convert Sorted List to Binary Search Tree - ALawliet/algorithms GitHub Wiki

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # T: O(nlogn) recursion
    # T: O(n) stack
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        def findMid(head):
            prev = None
            fast = head
            slow = head
            
            while fast and fast.next:
                prev = slow
                slow = slow.next
                fast = fast.next.next
                
            # if prev:
            prev.next = None
            
            # break the left and right on slow because this will be new mid
            return slow
        
        if not head: return None
        if not head.next: return TreeNode(head.val)
        
        mid = findMid(head)
        root = TreeNode(mid.val)
        # if head == mid: return root
        root.left = self.sortedListToBST(head) # head up to mid (without it)
        root.right = self.sortedListToBST(mid.next) # after mid
        
        return root