题解 | #在二叉树中找到两个节点的最近公共祖先#

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整型
     */

    /**
     我们只要往上找，找到他们第一个相同的公共祖先节点即可，
     但怎么找到每个节点的父节点呢，我们只需要把每个节点都遍历一遍，
     然后顺便记录他们的父节点存储在Map中。
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        Map<Integer, Integer> map = new HashMap<>();
        Queue<TreeNode> que = new LinkedList<>();
        map.put(root.val, -1);
        que.add(root);
        // 只有两个节点都搜索到，才会停止遍历
        while (!map.containsKey(o1) || ! map.containsKey(o2)) {
            TreeNode ptr = que.poll();
            if (ptr.left != null) {
                que.add(ptr.left);
                map.put(ptr.left.val, ptr.val);
            }
            if (ptr.right != null) {
                que.add(ptr.right);
                map.put(ptr.right.val, ptr.val);
            }
        }
        Set<Integer> ancestor = new HashSet<>();
        while (map.containsKey(o1)) {
            ancestor.add(o1);
            o1 = map.get(o1);
        }

        while (!ancestor.contains(o2)) {
            o2 = map.get(o2);
        }
        return o2;
    }
}