Python solution in O(n) (update to faster version)


  • 3
    A
    def cover(self, root, target):
        if root == None:
            return False
        if root == target:
            return True
        return self.cover(root.left, target) or self.cover(root.right, target)
        
    def lowestCommonAncestor(self, root, p, q):
        if root == None or root == p or root == q:
            return root
            
        if self.cover(p, q):
            return p
        if self.cover(q, p):
            return q
    
        def helper(root, p, q):
            p_left = self.cover(root.left, p)
            q_left = self.cover(root.left, q)
            if p_left != q_left:
                return root
            if p_left:
                return helper(root.left, p, q)
            else:
                return helper(root.right, p, q)
                
        return helper(root, p, q)
    

    The time is O(N) because it's n+ n1/2 + n1/4 + n*1/8...


  • 0
    W

    maybe you should leave

    if self.cover(p, q):
        return p
    if self.cover(q, p):
        return q
    

    outside the "lowestCommonAncestor", since when you recurse on node.left/ node.right
    you are doing the cover again...I think it only needs to be checked once

    here is the body of my lowestCommonAncester function, what we do is mostly the same
    except that my cover(p,q) and cover(q,p) are only executed once

    def lowestCommonAncestor(self, root, p, q):
        if cover(p,q):
            return p
        if cover(q,p):
            return q
    
        def helper(node,x,y):
            if node is None:
                return None
            if node is x or node is y:
                return node
            left = helper(node.left,x,y)      # you called lowestCommonAncestor, which will compyte cover(p,q) again
            right = helper(node.right,x,y)
            if left and right:
                return node
            if left:
                return left
            if right:
                return right
        return helper(root,p,q)

  • 0
    A

    I am not sure what you are talking about. I think my code is right. Can you modify it and submit your version to OJ? Then paste it here.


  • 0
    W

    I put up my code, please let me know if it make sense


  • 0
    A

    yes, you are right! I update my code.


Log in to reply
 

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