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.

解题方法

这道题因为list没有random access，所以需要每次找到中点，然后再对两边recursive的构建，所以比较繁琐。

也可以采用bottom-up的方法，不断地构建左子树，让list pointer的位置随着左子树的构建而变化，这样能够一次遍历构建

Solution

bottom-up

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

        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next

        root, cur = self.helper(head, 0, length - 1)
        return root

    def helper(self, cur, start, end):
        if start > end:
            return None, cur

        mid = start + (end - start) / 2
        # cur doesn't change with function call cause it's not a class variable, so need return to update the cur position
        left, cur = self.helper(cur, start, mid - 1)
        root = TreeNode(cur.val)
        cur = cur.next
        right, cur = self.helper(cur, mid + 1, end)

        root.left = left
        root.right = right

        return root, cur

Reference

• convert 2 BST