109-Convert-Sorted-List-to-Binary-Search-Tree
# 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
"""
self.curNode = head
n = 0
p = head
while p:
n += 1
p = p.next
return self.toBST(0, n-1)
def toBST(self, start, end):
if start > end:
return None
mid = (start + end) / 2
#######################
leftNode = self.toBST(start, mid-1)
#######################
node = TreeNode(self.curNode.val)
self.curNode = self.curNode.next
rightNode = self.toBST(mid+1, end)
#######################
node.left = leftNode
node.right = rightNode
return node
# 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
"""
return self.toBST(head, None)
def toBST(self, head, tail):
if head == tail:
return None
slow = head
fast = head
while fast != tail and fast.next != tail:
fast = fast.next.next
slow = slow.next
curNode = TreeNode(slow.val)
curNode.left = self.toBST(head, slow)
curNode.right = self.toBST(slow.next, tail)
return curNode
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/#/solutions
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.