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;
    }
}