medium

Question

加一個(gè)升序鏈列轉(zhuǎn)化為height balanced BST

Solution

此題與Convert Sorted Array to Binary Search Tree有序數(shù)列構(gòu)建BST非常類似，但是有序數(shù)列變成了有序鏈列。

第一個(gè)方法當(dāng)然是把鏈列轉(zhuǎn)化為數(shù)列再套用上面的方法。

# 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

由于需要先轉(zhuǎn)化，如果要求不能轉(zhuǎn)化呢。現(xiàn)在考慮直接從鏈列入手。下面的算法使用兩個(gè)指針，一快一慢，來(lái)找到鏈列的中間值。處理方法與有序數(shù)列類似。

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). 下面看一個(gè)bottom-up的approach，這樣可以依照順序利用鏈列。top-down的方法經(jīng)常需要重復(fù)計(jì)算，這個(gè)時(shí)候bottom-up是應(yīng)該考慮的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