Simple recursive Java solution, O(n)


  • 3
    M
    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 left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            // we found nodes in both the sides, so return root.
            if( left != null && right != null )
                return root;
            return ( left != null )? left : right;
        }
    
    }
    

  • 0
    K

    @mandalapusc.edu Nice one!!


  • 0
    S
    This post is deleted!

  • 0
    M

    @saneGuy It returns 37 as the lowest common ancestor which is not false when you consider -100 in the left subtree and -71 in the right subtree. There would be a conflict if we provide duplicate node values which happened in the test case provided. The very important thing that we need to understand is, we are comparing the entire nodes instead of values, so when you ask me to find lowest common ancestor to -100 and -71 nodes, pass the references instead. Not just the node values. :)


  • 0
    S

    @mandalapusc-edu makes sense ...thanks


  • 0
    M

    @saneGuy No worries....:) Happy Coding!


Log in to reply
 

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