My 4-lines Java solution


  • 12

    Just blind try left and right. Then if we find in both left and right side return root, otherwise return the one we got.

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

  • 0
    M

    Thank you! Really concise and elegant solution!


  • 0
    V

    This solution is giving 8 instead of 3 for the below tree (Root is 8) for the below calls:


    TreeNode _4 = new TreeNode(4, null, null);

    TreeNode _7 = new TreeNode(7, null, null);

    TreeNode _6 = new TreeNode(6, _4, _7);

    TreeNode _1 = new TreeNode(1, null, null);

    TreeNode _3 = new TreeNode(3, _1, _6);

    TreeNode _13 = new TreeNode(13, null, null);

    TreeNode _14 = new TreeNode(14, _13, null);

    TreeNode _10 = new TreeNode(10, null, _14);

    TreeNode _8 = new TreeNode(8, _3, _10);


    lowestCommonAncestor(tree, new TreeNode(1), new TreeNode(7)));

    lowestCommonAncestor(tree, new TreeNode(7), new TreeNode(1)));

    lowestCommonAncestor(tree, new TreeNode(10), new TreeNode(13)));

    lowestCommonAncestor(tree, new TreeNode(13), new TreeNode(10)));

    lowestCommonAncestor(tree, new TreeNode(3), new TreeNode(7)));

    lowestCommonAncestor(tree, new TreeNode(7), new TreeNode(7)));


  • 0
    R

    @venkateswaran2 It works for me using your tree.
    I don't understand your calls. After building the tree, are you actually calling what you wrote?

    lowestCommonAncestor(tree, new TreeNode(1), new TreeNode(7)));
    

    You should be calling:

    lowestCommonAncestor(_8, _1, _7);
    

  • 0
    C

    very nice solution! Incase anyone looking for the complete solution refer below

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            // This is the base case 
            if(root == p || root == q || root == null){
                return root;
            }
            
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            
            // common ancestor found
            if(left != null && right != null){
                return root;
            }
            
            // only left child found
            if(left != null){
                return left;
            }
            
            // only right child found
            return right;
        }
    
    

  • 0
    G

    @chiranjeeb2

    can u explain why left and right both are not null, then we return root ? I manually worked on a case and got correct answer.
    but intuitively it doesn't seem correct. take the example in the question as a case, the LCA of 5 & 1 is 3

    then calling your method
    LCA(3, 5, 1)
    {
    .......left = LCA(5, 5, 1) // here we got left is 5
    ........right = LCA(1, 5, 1) // here we got right is 1
    ........if ( left != null && right != null) //finally we return 3, which is correct answer.
    ................return root;
    }

    however reading "left = LCA(5, 5, 1)", Shouldn't it be "find the LCA of node 5 and node 1 under the root 5".
    Since node 1 is not under root 5 at all, so LCA(5, 5, 1) should return NULL intuitively.

    I know it gives correct answer, however I still don't quite understand..


  • 0
    V

    @Richard.SF Thanks for your reply. It was my bad.


Log in to reply
 

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