AC Python recursive solution


  • 0
    def _toBST(self, head, tail):
        if head == tail:
            return None
        slow = fast = head
        while fast != tail and fast.next != tail:
            slow = slow.next
            fast = fast.next.next
        root = TreeNode(slow.val)
        root.left = self._toBST(head, slow)
        root.right = self._toBST(slow.next, tail)
        return root
    
    def sortedListToBST(self, head):
        return self._toBST(head, None)
    
    # 32 / 32 test cases passed.
    # Status: Accepted
    # Runtime: 288 ms
    # 57.14%
    

    The solution does not rely on the count of nodes to determine the middle/root node in the sorted list. Instead, we can use two pointers to find out the middle case. This will cause some overhead but it quick easy to implement.


Log in to reply
 

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