package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

public class _1644 {
    public static class Solution1 {
        /**
         * This is my not so elegant but original solution to get it accepted.
         */
        boolean[] exists = new boolean[2];

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            exists(p, root, 0);
            exists(q, root, 1);
            if (!exists[0] || !exists[1]) {
                return null;
            }
            return dfs(root, p, q);
        }

        private void exists(TreeNode target, TreeNode root, int index) {
            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);
            }
        }

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

@@ -1489,11 +1489,701 @@
  %7D%0A    %7D
+%0A%0A    public static class Solution2 %7B%0A        int found = 0;%0A%0A        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) %7B%0A            TreeNode lca = lca(root, p, q);%0A            return found == 2 ? lca : null;%0A        %7D%0A%0A        private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) %7B%0A            if (root == null) %7B%0A                return root;%0A            %7D%0A            TreeNode left = lca(root.left, p, q);%0A            TreeNode right = lca(root.right, p, q);%0A            if (root == p %7C%7C root == q) %7B%0A                found++;%0A                return root;%0A            %7D%0A            return left == null ? right : right == null ? left : root;%0A        %7D%0A    %7D
 %0A%7D%0A

add a solution for 1644