Recursively solve this problem

  • 2

    In order to find the LCA, I have to find some root, (p == root or p in root.left) and (q == root or q in root.right), now let check(r, p, q) to judge whether p or q is in the subtree of r. a1 = check(root.left, p, q), a2 = check(root.right, p, q) then if a1 or a2 is not none, a1 or a2 should be the first appearance of the q or p, it will be the answer, else r should be the answer.

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

Log in to reply

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