# 0236. Lowest Common Ancestor of a Binary Tree
###### tags: `Leetcode` `Medium` `DFS` `Lowest Common Ancestor`
Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
## 思路
和下面两题思路很像，建议复习的时候把所有LCA的题目一起看
[1676. Lowest Common Ancestor of a Binary Tree IV](https://hackmd.io/rfFxWl_vSpmNuuDBZnDChQ)
[1644. Lowest Common Ancestor of a Binary Tree II](https://hackmd.io/ZQcxIr0ATdGsU7OHP3NTdg)
### 思路一
递归
如果一个node 左右两边的subtree都有target node那么就返回他本身 否则就返回左边subtree或者右边subtree的LCA
### 思路二
记录父节点

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root in (None, p, q): return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right: return root
        if left: return left
        return right

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || 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) return root;
        if(left!=null) return left;
        return right;
    }
}

### 思路二

class Solution {
    Map<Integer, TreeNode> parents = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    boolean foundP = false, foundQ = false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        while(p!=null){
            visited.add(p.val);
            p = parents.get(p.val);
        }
        while(q!=null){
            if(visited.contains(q.val)){
                return q;
            }
            q = parents.get(q.val);
        }
        return null;
    }
    public void dfs(TreeNode root, TreeNode p, TreeNode q){
        if(foundP && foundQ) return;
        if(root == null){
            return;
        }
        if(root.left != null){
            parents.put(root.left.val, root);
            dfs(root.left,p,q);
        }
        if(root.right != null){
            parents.put(root.right.val, root);
            dfs(root.right,p,q);
        }
        if(root==p) foundP = true;
        if(root==q) foundQ = true;
    }
}