题目描述

给定一颗二叉树和两个任意节点，请求解出这两个节点的最小公共父节点，如果其中一个节点本身是另外一个的父类，那么就返回这个父节点，否则，就返回距离他们俩最近的公共父节点。此题给定的两个节点肯定在这颗二叉树中。

思路分析

常规思路，二叉树只能从父节点到孩子节点遍历，从孩子节点往上回溯比较困难，因此，此题既然要求求出最小公共父节点，那么，就构造一个从孩子节点回溯父节点的数据结构，用map保存孩子节点对应的父节点。
然后，从给定的两个节点中的任意一个开始向上回溯父节点，将路径上的所有节点都放入set中，然后，再回溯另一个，每遍历到一个父节点就在set中查找是否存在，返回找到的第一个节点，就是最小公共父节点。

代码

public static Node get(Node head,Node n1,Node n2){
        HashMap<Node,Node> map=new HashMap<>();
        map.put(head,head);
        getMap(map,head);
        HashSet<Node> set=new HashSet<>();
        while (n1!=head){
            set.add(n1);
            n1=map.get(n1);
        }
        set.add(head);
        while (true){
            if(set.contains(n2)){
                return n2;
            }else {
                n2=map.get(n2);
            }
        }
    }

    private static void getMap(HashMap map,Node node) {
        if(node==null){
            return;
        }
        Node left=node.left;
        Node right=node.right;
        if(left!=null){
            map.put(left,node);
        }
        if(right!=null){
            map.put(right,node);
        }
        getMap(map,left);
        getMap(map,right);
    }

思路二

总体思路是想利用递归向上返回的值来返回最小公共父节点。
分析题目的两种情况：
情况一：n1或者n2本身是另一个的父类节点，那么，最终结果应该是这个父节点本身。因此，向上返回的数据，返回它本身就可以了，如果它下面有另一个，也返回它自己本身就行，这样就会把下面的覆盖掉。然后，其余节点，如果不是n1和n2，就返回null，如果接收的返回值包含n1或者n2，就继续向上传递。
情况二：n1和n2本身没有父子关系，他们有一个公共的父节点，那么，向上传递的信息，n1或者n2就传递他们本身，但是，和上面有一点不同的地方在于，其余节点，有可能接收的返回值包含n1和n2两个，那么，其实这个节点就是最小的公共父类节点，因此，如果接收的左右孩子分别为n1和n2，那么，就返回他自己本身。其余节点还是接收什么就原样向上返回。
因此，总结一下上面分析的结果，向上返回的数据：
本身为n1或者n2，就向上返回自己
接收两个的话，就返回自己
如果接收一个，就原样照抄返回
自己不是n1和n2，且没有接收，就返回null

代码

    public static Node getFather(Node node,Node n1,Node n2){
        if(node==null||node==n1||node==n2){
            return node;
        }
        Node left=getFather(node.left,n1,n2);
        Node right=getFather(node.right,n1,n2);
        if(left!=null&&right!=null){
            return node;
        }
        return left!=null ? left:right;
    }

关于如何求二叉树2个节点的最小公共父节点，分2种情况讨论

情况1：节点有parent节点

           这种情况就直接找到节点1和节点2的根节点，然后求得2个链表的长度，再求得长度差。如果说2条链子的长度差为n，那么

 就长的节点先移动n步，然后和短的节点一起移动，并且判断父节点是否相等。那么这边其实也解决了另一个问题，就是求2个链表

 的交点。

            public static Node publicNode(Node node1,Node node2){

            //接下来是求2个条链的起始点

            int length1 = getLength(node1);

            int length2 = getLength(node2);

           Node firstNode,secondNode;

            int res = 0;

            if(length1>=length2)

            res = length1 - length2;

            for(int i = 0;i<res;i++){

            firstNode = firstNode.parent;

            }

            else{

            res = length2 - length1;

            for(int i = 0;i<res;i++){

            secondNode = secondNode.parent;

            }

          // 接下来是从起始节点开始找交点

           while(firstNode.parent!=null||secondNode.parent!=null){

                      if(node1.parent==node2.parent)

                      return node1.parent;

                      else{

                         firstNode = firstNode.parent;

                         secondNode = secondNode.parent;

                      }

           }

           }

       其实会这么一个问题，就会求链表的交点和求二叉树的2个节点的最小公共父节点了。

  情况2，节点没有parent节点

  这个其实也简单，就是从根节点开始层次遍历这棵树，然后判断当前节点是否包含2个节点，如果包含就继续遍历当前节点的

  左右节点是否包含这2个节点，如果包含就继续深入。如果左右都不包含，那么当前节点就是最小公共父节点。

  public static Node getPublicNode(Node node1,Node node2){

            //获得根节点,并且对根节点进行层次遍历

            Node root = getRoot(node1);

            Deque<Node> deque = new Deque<Node>();

            deque.add(root);

            while(deque.size()!=0){

            Node node = deque.peekFirst();

            if(node.containChilds(node1,node2)){

             //当当前节点包含2个节点，而它的左右节点都不包含2个节点，那么它就是最小公共父节点

            if(node.left!=null&&node.right!=null&&!node.right.containChilds&&!node.left.containChilds){

             return node;

             }

            if(node.left!=null&&node.left.containChilds(node1,node2))

            deque.add(node.left);

           if(node.right!=null&&node.right.containChilds(node1,node2))

            deque.add(node.right);

            }

           }

 }