-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0109 [M] Convert Sorted List to Binary Search Tree
Code with Senpai edited this page Feb 15, 2022
·
1 revision
# 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
footer