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

  • 0

    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:
    			root.left = self.buildTree(lHead)
    			root.left = TreeNode(lHead.val)
    	if rHead:
    			root.right = self.buildTree(rHead)
    			root.right = TreeNode(rHead.val)
    	return root
    def partition(self, head):
    	if not head:
    		return None
    	#only one node
    	if not 
    		return None, head, None
    	# only two nodes
    	if and not 
    		return None, head, 
    	# only three nodes
    	if and and not
    		mid, =, None
    		return head, mid,
    	# 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,
    	while fast and
    		slow =
    		fast =
    	mid, =, None
    	return head, mid,

  • 0

    Gets a runtime error for input [].
    Don't need to recheck and 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.