Share my 168 ms Python Solution


  • 0
    W
    def lowestCommonAncestor(self, root, p, q):
    	stack = [[root, False]]
    	pFind = False
    	qFind = False
    	ancestor = None
    
    	while stack:
    		curr, visited = stack.pop()
    		if curr is not None:
    			if visited:
    				# update temporary ancestor
    				if curr.left is ancestor or curr.right is ancestor:
    					ancestor = curr
    				# p and q occupy each side of tree respectively
    				if curr is root and (qFind or pFind):
    					return root
    			else:
    				# Find both nodes
    				if (pFind and curr is q) or (qFind and curr is p):
    					return ancestor
    
    				if curr is p:
    					pFind = True
    					ancestor = p
    				elif curr is q:
    					qFind = True
    					ancestor = q
    
    				stack.append([curr, True])
    				stack.append([curr.right, False])
    				stack.append([curr, True])
    				stack.append([curr.left, False])

Log in to reply
 

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