Python solution with detailed explanation


  • 0
    G

    Solution

    Convert Sorted List to Binary Search Tree https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/?tab=Description

    Algorithm

    • Design a split method that returns the left list, root, and right list.
    class Solution(object):
        def split(self, head):
            slow = head
            fast = head.next
            if fast:
                fast = fast.next
            else:
                return None, head, None
            while fast and fast.next:
                slow = slow.next
                fast = fast.next
                if fast:
                    fast = fast.next
            second = slow.next
            slow.next = None
            root = second
            second = second.next
            root.next = None
            return head, root, second
        
        def sortedListToBST(self, head):
            if head == None:
                return None
            head, root, second = self.split(head)
            tnode = TreeNode(root.val)
            tnode.left = self.sortedListToBST(head)
            tnode.right = self.sortedListToBST(second)
            return tnode
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.