将一个升序链表转为有序二叉树 和上一题的不同仅仅是将数组换成了链表
# 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 sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if len(nums) == 0:
return None
if len(nums) == 1:
return TreeNode(nums[0])
if len(nums)%2 == 1:
tree = TreeNode(nums[len(nums)/2])
tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)])
tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
else:
tree = TreeNode(nums[len(nums)/2-1])
tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)-1])
tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
return tree
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
array = []
if head:
while head:
array.append(head.val)
head = head.next
return self.sortedArrayToBST(array)
return []
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a list node
# @return a tree node
def convert(self,head,tail):
if head==tail:
return None
if head.next==tail:
return TreeNode(head.val)
mid=head
fast=head
while fast!=tail and fast.next!=tail:
fast=fast.next.next
mid=mid.next
node=TreeNode(mid.val)
node.left=self.convert(head,mid)
node.right=self.convert(mid.next,tail)
return node
def sortedListToBST(self, head):
return self.convert(head,None)
第一种方法比第二种在运算速度上要快
这题直接从上一题自己的代码改的,要说有什么总结直接看上一题就好了。