109.Convert Sorted List to Binary Search Tree Leetcode Pytho

Convert Sorted List to Binary Search Tree Total Accepted: 32343 Total Submissions: 117376 My Submissions Question Solution

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST

这题和convert array to binary search tree不同点在与LinkedList 没有random access所以要想找到中点只能利用fast 和slow pointer来查找。

这种方法比直接把linkedlist转成array要慢。

代码如下：

# 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 = Noneclass Solution:# @param head, a list node# @return a tree nodedef convert(self,head,tail):if head==tail:return Noneif head.next==tail:return TreeNode(head.val)mid=headfast=headwhile fast!=tail and fast.next!=tail:fast=fast.next.nextmid=mid.nextnode=TreeNode(mid.val)node.left=self.convert(head,mid)node.right=self.convert(mid.next,tail)return nodedef sortedListToBST(self, head):return self.convert(head,None)

，积极思考造成积极人生，消极思考造成消极人生。