JZ86 在二叉树中找到两个节点的最近公共祖先

题目

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

注：本题保证二叉树中每个节点的val值均不相同。

方法 BFS，非递归方法

思路

算法实现

看到6和7公共祖先有5和3，但最近的是5。我们只要往上找，找到他们第一个相同的公共祖先节点即可，
但怎么找到每个节点的父节点呢，我们只需要把每个节点都遍历一遍，
然后顺便记录他们的父节点存储在Map中。我们先找到其中的一条路径，
比如6→5→3，然后在另一个节点往上找，由于7不在那条路径上，
我们找7的父节点是2，2也不在那条路径上，
我们接着往上找，2的父节点是5，5在那条路径上，所以5就是他们的最近公共子节点。

代码

package mid.JZ86在二叉树中找到两个节点的最近公共祖先;

import java.util.*;

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> queue = new LinkedList<>();
        //记录父节点
        Map<Integer, Integer> parent = new HashMap<>();
        parent.put(root.val, Integer.MIN_VALUE);
        queue.add(root);
        //BFS
        while (!parent.containsKey(o1) || !parent.containsKey(o2)) {
            TreeNode node = queue.poll();
            //左子树
            if (node.left != null) {
                //记录父亲节点
                parent.put(node.left.val, node.val);
                queue.add(node.left);
            }
            //左子树
            if (node.right != null) {
                //记录父亲节点
                parent.put(node.right.val, node.val);
                queue.add(node.right);
            }
        }

        //记录祖先节点
        Set<Integer> ancestors = new HashSet<>();
        //列出o1的所有祖先节点
        while (parent.containsKey(o1)) {
            ancestors.add(o1);
            o1 = parent.get(o1);
        }

        while(!ancestors.contains(o2)) {
            o2 = parent.get(o2);
        }
        return o2;
    }
}