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...
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)
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.