1676. Lowest Common Ancestor of a Binary Tree IV

this Q is for n nodes:

just like 236 count solution, count == n is the ans

T: O(n)

S: O(n)

class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        dfs(root, nodes);
        return res;
    }
    private int dfs(TreeNode root, TreeNode[] nodes) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left, nodes);
        int right = dfs(root.right, nodes);
        int self = 0;
        for (TreeNode node : nodes) {
            if (node.val == root.val) {
                self = 1;
                break;
            }
        }
        int count = left + right + self;
        if (count == nodes.length && res == null) {
            res = root;
        }
        return count;
    }
}

use hashset to accelerate speed

class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        Set<Integer> nodesSet = new HashSet<>();
        for (TreeNode node : nodes) {
            nodesSet.add(node.val);
        }
        dfs(root, nodesSet);
        return res;
    }
    private int dfs(TreeNode root, Set<Integer> nodesSet) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left, nodesSet);
        int right = dfs(root.right, nodesSet);
        int self = 0;
        if (nodesSet.contains(root.val)) {
            self = 1;
        }
        int count = left + right + self;
        if (count == nodesSet.size() && res == null) {
            res = root;
        }
        return count;
    }
}