Another simple Java solution with Explanation for all conditions


  • 0
    A
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q){
                return root;
            }
            
            TreeNode l1 = lowestCommonAncestor(root.left, p,q);
            TreeNode r1 = lowestCommonAncestor(root.right, p,q);
            
            if(l1==null && r1==null){
              return null;  
            } 
            if(l1 !=null && r1!=null) return root; //means that l1 and r1 are on either side and they became so just after this root.
            return l1==null?r1:l1;
      }
    

    Explanation:
    keep building ur way down. U will get it.

    0_1473862662036_lca.png
    And now think of p and q as 6 and 9. The answer would be 0. At 0 they become on the either sides, so u return root. At 2, both left and right were null, so u return null. At 1, left subtree is returning(make sure it should return 0) a 0, and right subtree returns null, so u want to throw '0' to the previous call ie; what ever was left since left was not null and right was null. But at 3, left is null and right is not null, so u keep whatever is your right ie; '0'.


Log in to reply
 

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