前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定二叉树根节点和两个树节点，判断两个树节点的最近公共祖先节点
如:

求 5 和 8 的最近公共祖先节点
结果为2

解决方案

方案一：
树类问题的万能方法，将问题问到每一个子树
每一层处理：每一个子树返回自己是否存在5、8节点，当前层判断是否已经出现了同时含有5、8 节点的树，如果已经有了则直接返回，如果没有则判断自己是否有。
方案二：
这种方案也是我最开始学算法时想到的，直接使用map存储每一个节点的父节点，然后从5开始到根节点的途径节点存储到列表list中，从8开始遍历第一次遇到list中存在的节点时，返回。
方案三：
这种方案比较繁琐，但是能够提供批量查询：
1、首先申请一个map1，map1中的key为节点，value为另一个map2，map2中的key为目标节点，value为map1的key和map2的key的共同祖先。
2、将每一个节点都遍历一次，经过两个过程：
过程一：当前节点的左右子树中的所有节点与当前节点的公共祖先都是当前节点
过程二：当前节点的左右子树中的所有节点之间的公共祖先都是当前节点
递归过程比较繁琐，需要理清楚才行，具体看代码实现.

代码编写

java语言版本

方案一：

    /**
     * 判断公共祖先
     * @param root
     * @param o1
     * @param o2
     * @return
     */
    public static MyTreeNode publicAncestors(MyTreeNode root, MyTreeNode o1, MyTreeNode o2){
        if (root == null || o1 == null || o2 == null){
            return null;
        }
        // 存储公祖先
        MyTreeNode[] record = new MyTreeNode[1];
        myProcess(root, o1, o2, record);
        return record[0];
    }

    /**
     * 每一层递归返回值包含：
     * 1、boolean数组长度为2， 0：是否包含5， 1是否包含8
     * 2、record长度为1，判断是否已经出现了公共祖先
     * @param root
     * @param o1
     * @param o2
     * @param record
     * @return
     */
    private static boolean[] myProcess(MyTreeNode root, MyTreeNode o1, MyTreeNode o2, MyTreeNode[] record) {
        if (root == null){
            return new boolean[]{false, false};
        }

        boolean[] leftR = myProcess(root.getLeft(), o1, o2, record);
        boolean[] rightR = myProcess(root.getRight(), o1, o2, record);
        // 首先判断是否已经存在公共祖先
        if (record[0] != null){
            // 已经出现公共祖先了，就直接返回
            return new boolean[]{true, true};
        }else {
            // 说明还没有出现公共祖先
            boolean[] curR = new boolean[2];
            curR[0] = leftR[0] || rightR[0];
            curR[1] = leftR[1] || rightR[1];
            if (curR[0] && curR[1]){
                record[0] = root;
            }else {
                // 判断一下自己
                if (root == o1){
                    curR[0] = true;
                }else if (root == o2){
                    curR[1] = true;
                }
            }
            return curR;
        }
    }

方案二：

    /**
     * 方法二：
     * 制作map，向上寻找公共祖先
     * @param root
     * @param r1
     * @param r2
     * @return
     */
    public static MyTreeNode publicAncestors2(MyTreeNode root, MyTreeNode r1, MyTreeNode r2){
        if (root == null || r1 == null || r2 == null){
            return null;
        }
        Map<MyTreeNode, MyTreeNode> map = CommonUtils.convertTree2Map(root);
        Set<MyTreeNode> r1Set = new HashSet<>();

        MyTreeNode cur = r1;
        while (map.containsKey(cur)){
            r1Set.add(cur);
            cur = map.get(cur);
        }
        cur = r2;
        while (map.containsKey(cur)){
            if (r1Set.contains(cur)){
                return cur;
            }
            cur = map.get(cur);
        }
        return null;
    }

方案三：

    /**
     * 方法三
     * 时间和空间都是n^2 但是可以计算出所有节点之间的最短公共祖先
     * @param root
     * @param r1
     * @param r2
     * @return
     */
    public static MyTreeNode publicAncestors3(MyTreeNode root, MyTreeNode r1, MyTreeNode r2){
        LowestTreeNodeHelper helper = new LowestTreeNodeHelper(root);
        return helper.getLowestAncestor(r1, r2);
    }

方案三辅助数据结构：

public class LowestTreeNodeHelper {

    /**
     * key 任意树中节点
     * value 当前节点到任意节点的最近公共祖先
     */
    private Map<MyTreeNode, Map<MyTreeNode, MyTreeNode>> map;


    private MyTreeNode head;

    /**
     * 给定树后开始初始化操作
     * @param head
     */
    public LowestTreeNodeHelper(MyTreeNode head) {
        this.map = new HashMap<>();
        this.head = head;
        initMap();
        fillMap();
    }

    /**
     * 将数据结构分配内存
     */
    private void initMap() {
        if (head == null){
            return;
        }
        initProcess(head);
    }

    private void initProcess(MyTreeNode head) {
        if (head == null){
            return;
        }
        map.putIfAbsent(head, new HashMap<>());
        initProcess(head.getLeft());
        initProcess(head.getRight());
    }

    /**
     * 计算所有节点之间的最近公共祖先
     * 1、每一个节点与自己的子节点公共祖先都是自己
     * 2、当前节点的左右子节点中的每一对子节点的祖先都是自己
     */
    private void fillMap() {
        // 先序遍历处理每一个子节点
        fill(this.head);
    }

    /**
     * 先序遍历处理每一个子节点
     * @param head
     */
    private void fill(MyTreeNode head) {
        if (head == null){
            return;
        }
        // 1、将当前节点作为头结点,每一个子节点和当前头结点的公共节点都是当前头结点
        initHead(head, head.getLeft());
        initHead(head, head.getRight());

        // 2、将当前节点的左节点和右节点之间进行遍历，公共祖先都是当前节点
        // ** 这里只需要一边就行，put的时候将另一边的也put进来
        initChild(head, head.getLeft(), head.getRight());

        // 处理左右节点
        fill(head.getLeft());
        fill(head.getRight());
        //initChild(head, head.getRight(), head.getLeft());
    }

    /**
     * 将head以及head的子节点的左右子树填充
     * @param head
     * @param left
     * @param right
     */
    private void initChild(MyTreeNode head, MyTreeNode left, MyTreeNode right) {
        if (head == null){
            return;
        }
        if (left != null){
            // 将head的左子树中所有节点丰富起来
            initEdge(head, left, right);
            // 遍历左边的每一个节点，将右边的每一个节点都写入map
            initChild(head, left.getLeft(), right);
            initChild(head, left.getRight(), right);
            //initChild(left, left.getLeft(), left.getRight());
        }
        // 右子节点就不用了，因为左边填充时，右边也是相互的
    }

    /**
     * 初始化左右子树之间
     * 遍历other
     * @param head 公共祖先
     * @param cur
     * @param other
     */
    private void initEdge(MyTreeNode head, MyTreeNode cur, MyTreeNode other){
        if (other == null){
            return;
        }
        if (map.get(cur) != null && map.get(other) != null){
            Map<MyTreeNode, MyTreeNode> curMap = map.get(cur);
            Map<MyTreeNode, MyTreeNode> otherMap = map.get(other);
            curMap.put(other, head);
            otherMap.put(cur,head);
        }
        initEdge(head, cur, other.getLeft());
        initEdge(head, cur, other.getRight());
    }

    private void initHead(MyTreeNode head, MyTreeNode child) {
        if (child == null){
            return;
        }
        Map<MyTreeNode, MyTreeNode> childMap = map.get(child);
        Map<MyTreeNode, MyTreeNode> headMap = map.get(head);
        // 孩子节点
        childMap.put(head, head);
        headMap.put(child, head);
        initHead(head, child.getLeft());
        initHead(head, child.getRight());
    }
    /**
     * 获取r1和r2的公共祖先
     * @param r1
     * @param r2
     * @return
     */
    public MyTreeNode getLowestAncestor(MyTreeNode r1, MyTreeNode r2){
        if (!map.containsKey(r1) || !map.containsKey(r2)){
            return null;
        }
        Map<MyTreeNode, MyTreeNode> r1Map = map.get(r1);
        return r1Map.get(r2);
    }

}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

方案一，现在你应该会相信二叉树问题的通用解法有多么通用了吧~
方案三，说实话这个方案三我用了40分钟才完成调试，很麻烦，但是helper一旦完成，查询任何两个节点的公共祖先都是O(1)的时间，特别是左右子树之间相互记录的过程递归起来比较麻烦，嵌套了三层递归。但是理清楚了就很好实现
还有一个重点就是方案三给我们提供了一种公共祖先判断的思路：
1、任何节点与自己子节点之间的共同祖先都是节点自己
2、任何节点的左右子树之间的共同祖先也都是自己
这两个规则也奠定了接下来的tarjan算法的遍历顺序，请看下回分解~

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！