Comment body goes here.public class Solution {
public int lca(TreeNode A, int B, int C) {
if(null == A){
return -1;
}
TreeNode lca = lcaRecurse(A, B, C);
if(null == lca){
// Neither B nor C is found
return -1;
}
if(lca.val != B && lca.val != C){
// If ancestor is found
return lca.val;
}
if((lca.val == B && contains(lca, C)) || (lca.val == C && contains(lca, B))){
// Case 1. One (out of B and C) is ancestor of another
return lca.val;
}
// Case 2. Only one (out of B and C) is present in complete tree
return -1;
}
private TreeNode lcaRecurse(TreeNode root, int B, int C){
if(null == root){
return null;
}
if(root.val == B || root.val == C){
// One of them is found, no need to go further down to its substrees
return root;
}
// Search left subtree
TreeNode left = lcaRecurse(root.left, B, C);
if(null != left && left.val != B && left.val != C){
// If ancestor is already found in left subtree
return left;
}
// Search right subtree
TreeNode right = lcaRecurse(root.right, B, C);
if(null != right && right.val != B && right.val != C){
// If ancestor is already found in right subtree
return right;
}
if(null != left && null != right){
// If B and C are found on different substrees
return root;
}else if(null != left || null != right){
// If B or C is found in left or right subtree
// It can happen ifn 2 cases
// Case 1. One (out of B and C) is ancestor of another
// Case 2. Only one (out of B and C) is present in complete tree
return (null != right)?right : left;
}
return null;
}
private boolean contains(TreeNode root, int value){
if(null == root){
return false;
}
if(root.val == value){
return true;
}
return contains(root.left, value) || contains(root.right, value);
}
}