# 1676. Lowest Common Ancestor of a Binary Tree IV
###### tags: `Leetcode` `Medium` `LCA` `DFS`
Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/
## 思路
和下面两题思路很像，建议复习的时候把所有LCA的题目一起看
[0236. Lowest Common Ancestor of a Binary Tree](https://hackmd.io/8Sj0WCYbRFadYo4hDTXcyg)
[1644. Lowest Common Ancestor of a Binary Tree II](https://hackmd.io/ZQcxIr0ATdGsU7OHP3NTdg)

由于这题所有node都会出现，所以对于任何一个node，只要它的左边包含targetnode，右边也包含targetnode，那么就回传这个node本身，否则哪边包含targetnode，就回传哪边（这样才能保证传到root的答案就是LCA)

**总结：做完所有LCA的题就会发现，如果是所有node都会出现，那么就正常写，也就是碰到一个targetnode，就返回不需要遍历它的child；如果有的node不会出现，那么要先dfs left和right，再写如果root=targetnode，就返回，让left和right继续跑，才能记下来一共经历了多少targetnode**
## Code

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        Set<TreeNode> tnodes = new HashSet<>();
        for(TreeNode node: nodes){
            tnodes.add(node);
        }
        return dfs(root, tnodes);
    }
    public TreeNode dfs(TreeNode root, Set<TreeNode> tnodes){
        if(root == null) return null;
        if(tnodes.contains(root)) return root;
        TreeNode left = dfs(root.left, tnodes);
        TreeNode right = dfs(root.right, tnodes);
        if(left!=null && right!=null) return root;
        if(left!=null) return left;
        else return right;
    }
}