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

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整型
     * 整体思路：由于树中的节点的值都不一样，所以可以使用HashMap<key,value>存储儿子-父亲键值对。HashMap<Integer,Integer>
                其中key:儿子，value:父亲。然后再从HashMap中取出那两个节点的父亲链（父亲，祖父，曾祖父。。。），
                父亲链用链表存储。最后在两条链中寻找最近的相同值。
     * 时间复杂度：O(n)
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        TreeNode root1 = root;
        
        preOrder(root1,hashMap);//先根遍历二叉树
        
        ArrayList<Integer> arrayList1 = new ArrayList<>();//创建一个链表，存放o1的父亲链
        int key1 = o1;
        //取出o1的父亲链
        arrayList1.add(o1);
        while(hashMap.containsKey(key1)){
            key1 = hashMap.get(key1);
            arrayList1.add(key1);
        }
        
        ArrayList<Integer> arrayList2 = new ArrayList<>();//创建一个链表，存放o2的父亲链
        int key2 = o2;
        //取出o2的父亲链
        arrayList2.add(o2);
        while(hashMap.containsKey(key2)){
            key2 = hashMap.get(key2);
            arrayList2.add(key2);
        }
        
        int len1 = arrayList1.size();
        int len2 = arrayList2.size();
        //寻找最近的公共祖先
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(arrayList1.get(i) == arrayList2.get(j)){
                    return arrayList1.get(i);
                }
            }
        }
        
        return root.val;
    }
    
    //先根遍历
    public void preOrder(TreeNode root,HashMap<Integer,Integer> hashMap){
        //递归出口
        if(root == null){
            return ;
        }
        //递归左子树
        if(root.left != null){
            hashMap.put(root.left.val,root.val);
            preOrder(root.left,hashMap);
        }
        //递归右子树
        if(root.right != null){
            hashMap.put(root.right.val,root.val);
            preOrder(root.right,hashMap);
        }
    }
}