https://leetcode.com/problems/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.
Code
# 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
"""
if head is None:
return None
prev_slow_pt = None
slow_pt = head
fast_pt = head
while fast_pt.next and fast_pt.next.next:
fast_pt = fast_pt.next.next
prev_slow_pt = slow_pt
slow_pt = slow_pt.next
root = TreeNode(slow_pt.val)
root.right = self.sortedListToBST(slow_pt.next)
if prev_slow_pt:
prev_slow_pt.next = None
root.left = self.sortedListToBST(head)
return root
Idea
To find the middle element in a linkedlist, it is a typical way to set two pointers, a slow pointer and a fast pointer. Let the fast one moves two elements forward every time while the slow one only moves one element forward each time. When the fast one reaches the end of the linkedlist, the slow pointer stops at the middle element of the linkedlist.
The slow pointer becomes the root of the BST. Then, all elements before the slow pointer become the left tree and all elements after the slow pointer become the right tree. The problem thus can be solved by smaller problems.
Note that I also maintain `prev_slow_pt` as a pointer pointing to the element right before the `slow_pt`. This is useful when you want to process only the elements from `head` to `prev_slow_pt` to form the left tree. (See line 33 – 35). If `prev_slow_pt` is None, it means `slow_pt` hasn’t moved at all and stayed at the `head` element. In this case, the left tree should be None.
In total, the time complexity is O(NlogN) where N is the number of elements in the linkedlist.
Idea II
However, repeatedly scanning the linkedlist using two pointers causes some waste in time. Another version that is more thrift in time would be using inorder traversal to construct the 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
"""
size = 0
self.head = head
while head is not None:
size += 1
head = head.next
return self.helper(0, size)
def helper(self, start, end):
'''
start: inclusive
end: exclusive
'''
if start >= end:
return None
mid = start + (end-start-1) / 2
left = self.helper(start, mid)
root = TreeNode(self.head.val)
self.head = self.head.next
right = self.helper(mid+1, end)
root.left = left
root.right = right
return root
Since, every node is traversed exactly once, the time complexity is O(N). If you consider stacks used in recursion, the space complexity is O(logN)