4 lines C++/Java/Python/Ruby


  • 318

    Same solution in several languages. It's recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.

    Update: I also wrote two iterative solutions now, one of them being a version of the solution here. They're more complicated than this simple recursive solution, but I do find them interesting.


    C++

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        return !left ? right : !right ? left : root;
    }
    

    Python

    def lowestCommonAncestor(self, root, p, q):
        if root in (None, p, q): return root
        left, right = (self.lowestCommonAncestor(kid, p, q)
                       for kid in (root.left, root.right))
        return root if left and right else left or right
    

    Or using that None is considered smaller than any node:

    def lowestCommonAncestor(self, root, p, q):
        if root in (None, p, q): return root
        subs = [self.lowestCommonAncestor(kid, p, q)
                for kid in (root.left, root.right)]
        return root if all(subs) else max(subs)
    

    Ruby

    def lowest_common_ancestor(root, p, q)
        return root if [nil, p, q].index root
        left = lowest_common_ancestor(root.left, p, q)
        right = lowest_common_ancestor(root.right, p, q)
        left && right ? root : left || right
    end
    

    Java

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left == null ? right : right == null ? left : root;
    }

  • 0

    Oh really? Let me fix that one quickly. :)


  • 0

    Which way? Make it possible for other languages or make it impossible for C++? :-)


  • 0

    Just fixed it for python, your solution should get Accepted. No offense to python lovers :)


  • 0

    Yeah, works now. Same problem with Java, though (and possibly Ruby, but maybe I have a different bug there).


  • 0

    Yeah, just fixed Java. Fixing the rest now...


  • 0

    Done. I have verified all of them are working now.


  • 0

    Thanks, mine work as well now. I was already wondering whether I'll have to write an iterative solution. That looks like a real challenge compared to recursion. I have some ideas, will still try them now...


  • 0
    C
    def lowestCommonAncestor(self, root, p, q):
        if not root or p == root or q == root:
            return root
        if self.lowestCommonAncestor(root.left, p, q) and self.lowestCommonAncestor(root.right, p, q):
            return root
        return self.lowestCommonAncestor(root.left, p, q) or self.lowestCommonAncestor(root.right, p, q)
    

    why does this python code not work? the idea is same to yours.


  • 0

    What do you mean it doesn't work?


  • 0
    C

    yes, TLE... but smaller input size is ok.


  • 2

    Ah, TLE. Well, you might go into each subtree twice. Which means you might go into each subsubtree four times. And into each subsubsubtree eight times. And so on. That takes exponential time, which is very slow.


  • 0
    C

    wow, got it. that's it. Thank you.


  • 0

    Looking forward to your iterative solution :-)


  • 6
    W

    This solution can not make sure p and q are in the tree. In my opinion, when one of p and q is not in the tree, the code should return null.


  • 1

    Hi, weizier. The problem statement has guaranteed this point: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.


  • 0

    @weizier In addition to what @jianchao.li.fighter said, I think that...

    • p and q should at the very least either be nodes in the tree or null. If they're something else, then the user is just being stupid.
    • If p is a node in the tree and q is null, then the LCA of the given nodes, i.e., the LCA of just p, truly is p itself. Not null.

  • 0

  • 0

    Sorry for my original erroneous comment. I made a mistake. || Original: I think the solution fails when root == p == q, which shall return root.


  • 0

    @zhiqing_xiao Why would that fail? My first line would directly return root.


Log in to reply
 

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