题解 | #第一个只出现一次的字符#

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) {
        //map用于存放<子节点的值，父节点的值>
        Map<Integer,Integer> parent = new HashMap<>();
        //队列用于遍历所有节点
        Queue<TreeNode> que = new LinkedList<>();
        //给root一个初始值，因为没有父节点
        parent.put(root.val,Integer.MIN_VALUE);
        //将root添加到队列，开始遍历
        que.add(root);

        //遍历树，直到找到o1和o2
        while(!parent.containsKey(o1) || !parent.containsKey(o2)){
            //先进先出，从队列中第一个节点开始，依次出队遍历左右子树
            TreeNode node = que.poll();
            //若节点的左孩子非空，则记录其与父节点的值到map，即<左孩子值，当前节点值>
            //同时将左孩子添加到队列准备遍历
            if(node.left != null){
                parent.put(node.left.val,node.val);
                que.add(node.left);
            }
            //右孩子同左孩子
            if(node.right!=null){
                parent.put(node.right.val,node.val);
                que.add(node.right);
            }
        }
        //从map中查询，并记录o1的所有父节点和祖先节点，添加到set中
        Set<Integer> ancestor = new HashSet<>();
        while(parent.containsKey(o1)){
            ancestor.add(o1);
            //获取o1的父节点，继续遍历
            o1 = parent.get(o1);
        }
        //查看o1和他的祖先节点是否包含o2节点,直到找到交叉点，即为所求
        while(!ancestor.contains(o2)){
            o2 = parent.get(o2);
        }
        return o2;

    }
}