Convert Linked List to Binary Search Tree
Problem: Convert Linked List to Binary Search Tree
The general idea is to find the center node of linked list and make it root of a tree. Then we do the same thing to its left part and right part to get left and right sub-tree. To find center node of a linked list, we can use two pointers, one going 2 steps ahead and one going 1 step. When the fast pointer gets to the end, the slow pointer gets to the middle node.
Code in Python:
# 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 not head: return None
def helper(head):
if not head: return None
if not head.next:
root = TreeNode(head.val)
return root
slow = fast = head
prev = None
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
root = TreeNode(slow.val)
root.left, root.right = helper(head), helper(slow.next)
return root
return helper(head)