_1644.java

packagecom.fishercoder.solutions.secondthousand;

importcom.fishercoder.common.classes.TreeNode;

publicclass_1644 {
publicstaticclassSolution1 {
/*
 * This is my not so elegant but original solution to get it accepted.
 */
boolean[] exists = newboolean[2];

publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
exists(p, root, 0);
exists(q, root, 1);
if (!exists[0] || !exists[1]) {
returnnull;
 }
returndfs(root, p, q);
 }

privatevoidexists(TreeNodetarget, TreeNoderoot, intindex) {
if (root == null) {
return;
 }
if (target == root) {
exists[index] = true;
return;
 }
if (!exists[index]) {
exists(target, root.left, index);
 }
if (!exists[index]) {
exists(target, root.right, index);
 }
 }

privateTreeNodedfs(TreeNoderoot, TreeNodep, TreeNodeq) {
if (root == null || p == root || q == root) {
returnroot;
 }
TreeNodeleft = lowestCommonAncestor(root.left, p, q);
TreeNoderight = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
returnroot;
 }
returnleft != null ? left : right;
 }
 }

publicstaticclassSolution2 {
/*
 * This still checks nodes existence.
 */
intfound = 0;

publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
TreeNodelca = lca(root, p, q);
returnfound == 2 ? lca : null;
 }

privateTreeNodelca(TreeNoderoot, TreeNodep, TreeNodeq) {
if (root == null) {
returnnull;
 }
TreeNodeleft = lca(root.left, p, q);
TreeNoderight = lca(root.right, p, q);
if (root == p || root == q) {
found++;
returnroot;
 }
return (left != null && right != null) ? root : left != null ? left : right;
 }
 }

publicstaticclassSolution3 {
/*
 * Credit: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/solutions/944963/beat-96-recursion-without-count-easy-understanding/
 */
publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
if (root == null || p == null || q == null) {
returnnull;
 }
TreeNoderesult = findLCA(root, p, q);
if (result == p) {
// if p equals result, we'll check the existence of q in the subtree of p
returnfindLCA(p, q, q) != null ? result : null;
 } elseif (result == q) {
// if q equals result, we'll check the existence of p in the subtree of q
returnfindLCA(q, p, p) != null ? result : null;
 }
// otherwise, it's this case: (p != result && q != result) || result == null
returnresult;
 }

privateTreeNodefindLCA(TreeNoderoot, TreeNodep, TreeNodeq) {
if (root == null || p == root || q == root) {
returnroot;
 }
TreeNodeleft = findLCA(root.left, p, q);
TreeNoderight = findLCA(root.right, p, q);
if (left != null && right != null) {
returnroot;
 }
returnleft != null ? left : right;
 }
 }
}