medium

Question

加一个升序链列转化为height balanced BST

Solution

此题与Convert Sorted Array to Binary Search Tree有序数列构建BST非常类似，但是有序数列变成了有序链列。

第一个方法当然是把链列转化为数列再套用上面的方法。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        ls = []
        p = head
        while p:
            ls.append(p.val)
            p = p.next
            
        return self.helper(ls)
    
    def helper(self, ls):
        try:
            mid = len(ls)/2
            root = TreeNode(ls[mid])
            root.left = self.helper(ls[:mid])
            root.right = self.helper(ls[mid+1:])
            return root
        except:
            return None

由于需要先转化，如果要求不能转化呢。现在考虑直接从链列入手。下面的算法使用两个指针，一快一慢，来找到链列的中间值。处理方法与有序数列类似。

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head:
            return 
        if not head.next:
            return TreeNode(head.val)
        dummy = ListNode(0)
        dummy.next = head
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        root = TreeNode(slow.next.val)
        root.right = self.sortedListToBST(slow.next.next)
        slow.next = None
        root.left = self.sortedListToBST(head)
        return root

上面的方法是top-down的，time complexity为O(n*logn). 下面看一个bottom-up的approach，这样可以依照顺序利用链列。top-down的方法经常需要重复计算，这个时候bottom-up是应该考虑的option。

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        n = 0
        p = head
        self.node = head
        while p:
            n += 1
            p = p.next
        return self.helper(0, n-1)
    
    def helper(self, start, end):
        if start > end:
            return None
        mid = (start+end)/2
        l = self.helper(start,mid-1)
        root = TreeNode(self.node.val)
        root.left = l
        self.node = self.node.next
        root.right = self.helper(mid+1,end)
        return root