10-line Java solution, solved in one traversal


  • 20
    public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        
        if(root == p || root == q){
            return root;
        }
        
        TreeNode l = lowestCommonAncestor(root.left,p,q);
        TreeNode r = lowestCommonAncestor(root.right,p,q);
        
        if(l != null && r != null){
            return root;
        }
        
        return l != null ? l:r;
    
    }
    

    }

    A modified version of pre-order traversal. The point to understand this is, once a sub-branch has a possible ancestor, all its super branches will have the same one.


  • 0
    H

    Very intelligent solution!! once P node belong to Q node's children. Q node should definitely be LCA, then ignore the recursive process of P.


  • 0
    C

    There is one problem with this algorithm, if the tree only contains the root node and the value is p or q, it will return root. But it should return null instead because the other value is not in the tree.


  • 1

    "of two given nodes in the tree." Specified by the question


  • 0
    S

    I don't think this is correct.
    e.g., a recursive call of lowestCommonAncestor will return true as long as p or q is the root, no matter whether the other node is below it.


  • 0

    What node would be above the root then?


  • 0
    L

    the problem is to solve finding the LCA of "two given nodes in the tree", not "two random nodes" , so the input would be always valid.


  • 2
    L
    TreeNode l = lowestCommonAncestor(root.left,p,q);
    TreeNode r = lowestCommonAncestor(root.right,p,q);
    
    if(l != null && r != null){
        return root;
    }
    

    It's really confusing to read these serveral lines of code. They show one thing but do other thing. As the name of method lowestCommonAncestor suggests, it is supposed to find the lowest ancestor of p and q. However, the author abuses the usage of the name and use it to find the node p or q in the subtrees. This is really bad, it forces readers to trace down the recursive method to understand what it really does!! I strongly suggest that using a help method with proper name to replace the method lowestCommonAncestor here.


  • 0
    M

    Can someone explain to me what is the worst case time complexity of this solution.
    Thanks


  • 0
    L

    clearly it's O(n). Cuz it just looks like DFS, only travese the tree once.


  • 0
    D
    This post is deleted!

  • 0
    J

    strongly agree. This is very confusing. When I first read the solution, I didn't understand why it came out with the right answer. Then I really the author abused the semantics of the method.


  • 0
    N

    The solution and many others in this question are against the definition of "recursion". Using it shows one do not fully understand the recursion, which is dangerous if you met a sharp interviewer.


  • 0

    After one year I wrote this, came back and read all these comments..

    I understand how irritated It could be when a simple solution like this working perfectly but you just can't figure out WHY.

    I didn't see any comment worthing arguing back but I do want to give my conclusion: without fully understanding what's going in every line of this method, your comprehension of recursion is not yet enough.

    The beauty of recursion is simplicity, the trade-off of simplicity is sometime hard to grasp the idea.


  • 0
    P

    Just to backup the author, this is actually a very beautiful solution as long as you really understand recursion.

    I used his method and programmed in Python for this problem a year back. I just thought that it was nice, but I could not write it myself back then. Now, not only can I write this one by myself, I can also write one for a similar but modified question. This is when I see how beautiful his answer is.


  • 0
    P
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            self.result = None
            # find p or q
            def dfs(node, p, q):
                if not node:
                    return node
                left = dfs(node.left, p, q)
                right = dfs(node.right, p, q)
                if (left and right) or ((left or right) and (node == p or node == q)):
                    self.result = node
                if node == p or node == q:
                    return node
                return left if left else right
            dfs(root, p, q)
            return self.result
    

    You can always be too careful with normal dfs to make sure that p and q are both in the tree. But when you can, why not use the fact that p and q are definitely in the tree like the author did?


Log in to reply
 

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