109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution: DFS

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """

        def dfs(head, tail):
            if head == tail:
                return None
            slow = fast = head
            while fast != tail and fast.next != tail:
                fast = fast.next.next
                slow = slow.next
            root = TreeNode(slow.val)
            root.left = dfs(head, slow)
            root.right = dfs(slow.next, tail)
            return root

        return dfs(head, None)

Related:

• 108. Convert Sorted Array to Binary Search Tree