# 1644. Lowest Common Ancestor of a Binary Tree II
###### tags: `Leetcode` `Medium` `LCA` `DFS`
Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/

## 思路
和下面两题思路很像，建议复习的时候把所有LCA的题目一起看
[0236. Lowest Common Ancestor of a Binary Tree](https://hackmd.io/8Sj0WCYbRFadYo4hDTXcyg)
[1676. Lowest Common Ancestor of a Binary Tree IV](https://hackmd.io/rfFxWl_vSpmNuuDBZnDChQ)

区别在于edge case的处理 （p是q的child，或者q是p的child)
- 236那题如果找到一个p或者q，就不需要再dfs 当前root的child了，因为child一定不是存在在 当前root的child里面，就是存在在剩余的tree里面
如果存在在当前root的child里面，那么当前node会原封不动的一直把答案（也就是当前root）传到最上面
- 但是1644这一题在找到一个p或者q之后还是需要向下遍历的，但是由于还是要找LCA，所以整体的代码不变，只是在找到p或者q之后还需要向下遍历，并且计数到底找到了几个target node（p和q)

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

## Code

class Solution {
    int count = 0;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = findLCA(root, p, q);
        if(count == 2) return node;
        return null;
    }
    public TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q){
        if(root==null) return root;
        
        TreeNode left = findLCA(root.left, p, q);
        TreeNode right = findLCA(root.right, p, q);
        
        if(root == p || root == q){
            count++;
            return root;
        }
        
        if(left!=null && right!=null){
            return root;
        }

        if(left!=null) return left;
        else return right;
    }
}