package com.jiucaiyuan.net.algrithm.tree;



import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;



/**

 * <pre>

 * 【问题】给定二叉树的两个节点node1和node2，找到他们最低公共祖先

 * 【概念】最低公共祖先：两个节点往root节点的链路，第一个相交的节点

 * 【思路】

 * </pre>

 *

 * @Author jiucaiyuan  2022/4/10 23:55

 * @mail services@jiucaiyuan.net

 */



public class LowestCommonAncestor {



    /**

     * <pre>

     * 最低公共祖先

     * 思路：从树中所有子树递归查找node1和node2，只要看到其一，就返回，左树和右树中都找到了，

     * 那么最低祖先一定是当前node，如果其中一个树找到了，另一个子树没有都找到，

     * 则一定是其中一个是另一个的祖先

     * </pre>

     * @param head

     * @param node1

     * @param node2

     * @return

     */

    public static Node lowestAncestor(Node head, Node node1, Node node2) {

        if (head == null || head == node1 || head == node2) {

            return head;

        }

        Node left = lowestAncestor(head.left, node1, node2);

        Node right = lowestAncestor(head.right, node1, node2);

        if (left != null && right != null) {

            return head;

        }

        return left != null ? left : right;

    }





    /**

     * 在head中找到node1和node2的最低公共祖先，node1和node2一定是head中的节点

     * 思路：先构建node1到head的整条链节点池，再访问node2到head节点路径，看那个再池中哪个就是

     *

     * @param head

     * @param node1

     * @param node2

     * @return

     */

    public static Node lca(Node head, Node node1, Node node2) {

        //构建整棵树的节点与父节点关系

        Map<Node, Node> fatherMap = new HashMap<>();

        fatherMap.put(head, head);

        process(head, fatherMap);



        //node1到父节点之间的节点放入set

        Set<Node> set = new HashSet<>();

        Node curr = node1;

        while (curr != fatherMap.get(curr)) {

            set.add(curr);

            curr = fatherMap.get(curr);

        }

        set.add(head);

        //再从node2开始逐个节点靠近head处理

        curr = node2;

        while (curr != fatherMap.get(curr)) {

            if (set.contains(curr)) {

                return curr;

            }

        }

        return head;

    }



    /**

     * 遍历head，把所有节点的和父节点的对应关系建立起来

     *

     * @param head

     * @param fatherMap

     */

    private static void process(Node head, Map<Node, Node> fatherMap) {

        if (head == null) {

            return;

        }

        fatherMap.put(head.left, head);

        fatherMap.put(head.right, head);

        process(head.left, fatherMap);

        process(head.right, fatherMap);

    }

}