120ms Python solution...


  • 3
    2

    I don't know what's going on. I'll admit if my solution is 100% correct, then the test cases might be too easy...

    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            if not root:
                return root
                
            left = self.lowestCommonAncestor(root.left, p, q)
            right = self.lowestCommonAncestor(root.right, p, q)
            
            if (p == root or q == root) or (left and right):
                return root
            else:
                return left if left else right

  • 1
    Z

    It took me a while to figure out how it works. The method basically pre-assumes that both p and q already resided in the given tree thus even if there is only one of p,q existing in the tree, the method still returns either p or q.
    Therefore the correctness of this method is automatically guaranteed.
    However, if one of the given p,q is absent from the tree at root, the method is not always correct. For example, when root is only q and both p and q are given.


Log in to reply
 

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