148ms Depth First Search Python Solution


  • 0
    Q

    I feel it could be cleaner, but it's a simple depth first search solution that was faster than I expected.

    def lowestCommonAncestor(self, root, p, q):
        def search(node):
            q_found = False
            p_found = False
            if node is None:
                return (False, False)
            
            if node is q:
                q_found = True
            if node is p:
                p_found = True
                
            result = search(node.left)
            if len(result) == 1:
                return result
            q_found = result[0] or q_found
            p_found = result[1] or p_found
            
            result = search(node.right)
            if len(result) == 1:
                return result
            q_found = result[0] or q_found
            p_found = result[1] or p_found
            
            if p_found and q_found:
                return (node,)
            else:
                return (q_found, p_found)
            
        result = search(root)
        if len(result) > 1:
            return None
        else:
            return result[0]

Log in to reply
 

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