236. Lowest Common Ancestor of a

LeetCode

Solution 1

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);

    if (left != null && right != null) {
        if (left != right) {
            return root;
        }
    }

    return left != null ? left : right;
}

Solution 2 with parent reference

public TreeNode lcaWithParent(TreeNode p, TreeNode q) {
    HashSet<TreeNode> set1 = new HashSet<>();
    HashSet<TreeNode> set2 = new HashSet<>();
    while (p != null || q != null) {
        if (p != null) {
            if (set2.contains(p)) {
                return p;
            }
            set1.add(p);
            p = p.parent;
        }

        if (q != null) {
            if (set1.contains(q)) {
                return q;
            }
            set2.add(q);
            q = q.parent;
        }
    }

    return null;
}

Solution 3

Find Two path and compare from root.

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    if (p == null || q == null) {
        return root;
    }
    Stack<TreeNode> pStack = new Stack<>();
    Stack<TreeNode> qStack = new Stack<>();
    findNodePath(p, root, pStack);
    findNodePath(q, root, qStack);

    TreeNode lowestAncestor = root;
    while (!pStack.isEmpty() && !qStack.isEmpty() && pStack.peek() == qStack.peek()) {
        lowestAncestor = pStack.pop();
        qStack.pop();
    }
    return lowestAncestor;
}

private void findNodePath(TreeNode target, TreeNode root, Stack<TreeNode> stack) {
    if (root == null) {
        return;
    }
    if (root == target) {
        stack.push(target);
        return;
    }
    findNodePath(target, root.left, stack);
    if (stack.size() > 0) {
        stack.push(root);
        return;
    }
    findNodePath(target, root.right, stack);
    if (stack.size() > 0) {
        stack.push(root);
        return;
    }
}