# 236 Lowest Common Ancestor of a Binary Tree

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

input是一棵Binary Tree的root，和兩個TreeNode p 和 q，要找出p和q的lowest common ancestor，並return。

宣告一個parentMap用來記錄每個TreeNode的Parent，

一個stack用來記錄traverse到哪個TreeNode。

1. 用dfs拜訪每一個TreeNode，每次拜訪某TreeNode就把它的parent記到parentMap裡。
2. 利用parentMap拜訪p的所有ancestor，並把p的所有ancestor放到一個HashSet中
3. 利用parentMap拜訪q的所有ancestor，直到找到一個q的ancestor存在於HashSet中，即為p,q的lowest common ancester

完整程式碼：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //use a parent map to record the parent of each node
        //create a stack for traverse tree

        //Concept:
        //while haven't found p and q in the given tree, -> not in map
        //  put (node,parent) into map
        //create a hashset 
        //add all ancestor of p in to hashset
        //trace q's ancestor through map, atill find an ancestor in hashset

        //Pseudocode:
        //stack.push(root)
        //while map doesn't contain p and q
        //  node = stack.pop()
        //  if(node.left!=null)
        //      stack.push(node.left)
        //      map.put(node.left, node)
        //  if(node.right!=null)
        //      stack.push(node.right)
        //      map.put(node.right, node)
        //Set<TreeNode> set = new HashSet<>();
        //while(p!=null)
        //  set.put(p);
        //  p = parent.get(p) -> p's parent
        //while(!set.contains(q))
        //  q = parent.get(q);
        // return q

        Map<TreeNode, TreeNode> parentMap = new HashMap<TreeNode,TreeNode>();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        parentMap.put(root,null);
        stack.push(root);
        while(!parentMap.containsKey(p) || !parentMap.containsKey(q)){
            TreeNode node = stack.pop();
            if(node.left!=null){
                parentMap.put(node.left, node);
                stack.push(node.left);
            }
            if(node.right!=null){
                parentMap.put(node.right, node);
                stack.push(node.right);
            }
        }

        Set<TreeNode> ancestor = new HashSet<>();
        while(p!=null){
            ancestor.add(p);
            p = parentMap.get(p);
        }
        while(!ancestor.contains(q))
            q = parentMap.get(q);
        return q;

    }
}