By far the fastest implementation in Python (160 ms) sharing


  • 0
    O

    I didn't expect the result would be that fast, because the thoughts are the same with what leetcode forum describe, nothing really tricky. But I think the code is not that concise, so if someone would also provide some suggestions, I would be really appreciated!

    def sortedListToBST(self, head):
    	return self.buildTree(head)
    
    def buildTree(self, head):
    	lHead, midNode, rHead = self.partition(head)
    	root = TreeNode(midNode.val)
    	if lHead:
    		if lHead.next:
    			root.left = self.buildTree(lHead)
    		else:
    			root.left = TreeNode(lHead.val)
    	if rHead:
    		if rHead.next:
    			root.right = self.buildTree(rHead)
    		else:
    			root.right = TreeNode(rHead.val)
    	return root
    
    
    def partition(self, head):
    	if not head:
    		return None
    	#only one node
    	if not head.next: 
    		return None, head, None
    	# only two nodes
    	if head.next and not head.next.next: 
    		return None, head, head.next 
    	# only three nodes
    	if head.next and head.next.next and not head.next.next.next:
    		mid, head.next = head.next, None
    		return head, mid, mid.next
    	# For list more than 4 nodes, separate list to 
    	# left list, root node, right list
    	# Using fast and slow pointers to find the root node
    	slow, fast = head, head.next
    	while fast and fast.next:
    		slow = slow.next
    		fast = fast.next.next
    	mid, slow.next = slow.next, None
    	return head, mid, mid.next
    

  • 0

    Gets a runtime error for input [].
    Don't need to recheck head.next and head.next.next for "only two/three nodes".
    Impressive speed.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.