寻找两个子节点最近公共祖先

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        Queue<TreeNode> q = new LinkedList<>();
        HashMap<Integer,Integer> parent = new HashMap<>();
        q.offer(root);
        parent.put(root.val,0);
        //BFS
        while(!parent.containsKey(o1)||!parent.containsKey(o2)){
            int count = q.size();
            while(count-- > 0){
                TreeNode t = q.poll();
                if(t.left != null){
                    q.offer(t.left);
                    parent.put(t.left.val,t.val);
                }
                if(t.right != null){
                    q.offer(t.right);
                    parent.put(t.right.val,t.val);
                }
            }
        }
        HashSet<Integer> flag = new HashSet<>();
        while(parent.containsKey(o1)){
            flag.add(o1);
            o1 = parent.get(o1);
        }
        while(!flag.contains(o2)){
            o2 = parent.get(o2);
        }
        return o2;
    }
}