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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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
        // 解题思路：
        // 1.采用前序遍历，找到每个节点自己的父节点值，保存在map中
        // 2.找到o1的所有父亲节点值
        // 3.判断o1所有父亲节点值是否包含o2，不包含则继续判断是否包含o2的父节点值

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(root.val, Integer.MIN_VALUE);
        getParent(root,  map);

        // 获取o1的所有祖先
        Set<Integer> o1Set  = new HashSet<>();
        while (map.containsKey(o1) ) {
            o1Set.add(o1);
            o1 = map.get(o1);
        }

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

        return o2;
    }

    private void getParent(TreeNode node, HashMap<Integer, Integer> map) {
        if (node == null) {
            return;
        }

        if (node.left != null) {
            map.put(node.left.val, node.val);
            getParent(node.left, map);
        }

        if (node.right != null) {
            map.put(node.right.val, node.val);
            getParent(node.right, map);
        }
    }
}