package tree;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 236. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
 *
 * @author Tang
 * @date 2021/7/22
 */
public class LowestCommonAncestor2 {

    Map<TreeNode, TreeNode> parentMap = new HashMap<>();

    /**
     * 纪录每个节点的父节点，记录到一个map中
     * 遍历p的父节点 存成一个List
     * 遍历q的父节点 判断是否在p的list中存在
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        preSearch(root);
        List<TreeNode> pParentList = new ArrayList<>();
        pParentList.add(p);
        TreeNode pParent = p;
        while(true){
            pParent = parentMap.get(pParent);
            if(pParent == null){
                break;
            }
            pParentList.add(pParent);
        }
        TreeNode qParent = q;
        while (true){
            if(pParentList.contains(qParent)) {
                return qParent;
            }
            qParent = parentMap.get(qParent);
            if(qParent == null){
                break;
            }
        }
        return null;


    }

    /**
     * 前序遍历 生成父节点Map
     *
     * @param node
     */
    private void preSearch(TreeNode node){
        if(node == null) {
            return;
        }
        if(node.left != null) {
            parentMap.put(node.left, node);
        }
        if(node.right != null) {
            parentMap.put(node.right, node);
        }
        preSearch(node.left);
        preSearch(node.right);
    }

    public static void main(String[] args) {


    }








}