左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver

题目

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

题解

解法一

设置一个 HashMap 保存节点与该节点的父节点（设根节点的父节点为本身），然后再用一个集合 set1 保存 node1 的全部祖先节点，对node2往上求祖先节点，看是否在 set1 中，若在，则这个节点即为最低公共祖先节点。

//前提：node1和node2一定属于head为头的树
//返回node1和node2的最低公共祖先
public static Node lca(Node head, Node node1, Node node2) {
    HashMap<Node, Node> fatherMap = new HashMap<>(); //保存节点与该节点的父节点
    fatherMap.put(head, head); //根节点的父节点为本身
    process(head, fatherMap);  //求所有节点的父节点
    HashSet<Node> set1 = new HashSet<>(); //node1 的祖先节点集合
    Node cur = node1;
    //求 node1 的祖先节点，并放入set1中 
    while (cur != fatherMap.get(cur)) { //回溯到根节点时停止
        set1.add(cur);
        cur = fatherMap.get(cur);
    }
    set1.add(head);

    //求 node2 的祖先节点
    cur = node2;
    while (!set1.contains(cur)) { //set1 中含该节点时停止
        cur = fatherMap.get(cur);
    }
    //该节点即为最低公共祖先节点
    return cur;
}
//递归求除根节点外所有节点的父节点，保存在 fatherMap 中
private static void process(Node head, HashMap<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);
}

解法二

在二叉树中有两种情况：

• 其中一个节点是另一个节点的子孙，则最低公共祖先节点是那个作为祖先的节点
• 两个节点不存在祖孙关系，则最低公共祖先节点是最近的公共祖先

试想这么一个递归操作：

• 基本事件是当一棵子树的头节点为 null 或 为 node1 或 node2 时，就返回这个头节点。
• 对左右子树作递归，获得左右子树的返回值。递归的返回值只有四种可能：null 、node1 、node2，两节点的最低公共祖先节点。
• 当左子树返回值不空，右子树返回值不空（即两节点分别落于左右子树上），返回头节点（该头节点即为最低公共祖先节点）。
• 当不满足左右子树返回值均不空这个条件时，若左子树返回值不空时返回该值（可能为node1 、node2，两节点的最低公共祖先节点），否则返回右子树的值（可能为null 、node1 、node2，两节点的最低公共祖先节点）。

在这个递归操作中，有以下情况：

• 若一棵子树不包含 node1 和 node2，那么它左右子树返回的值必定是 null，它往上返回的值也必定是 null；(a)

• 若一棵子树只包含 node1 和 node2 两者之一，这里假设包含的是node1，那么它往上返回的值是 node1；(b)

• 若一棵子树包含node1 和 node2 两者，

  • 若 node1 和 node2 存在祖孙关系，那么node1 和 node2 只能存在于该树的左右子树其中一棵，假设 node1 为 祖先（node1是最低公共祖先节点），则该树的左右子树返回值必定是node1和null，根据递归操作的最后一条原则，不管是左子树返回值是node1 还是右子树返回值是node1，都能保证该树往上返回的是 node1。

  • 若 node1 和 node2 不存在祖孙关系，分别落于它的左右子树中 ，根据(b)，则左右子树返回的值分别是node1和node2，即满足左右子树返回值均不空，那么该子树往上返回的值是头节点。(c)

  • 若 node1 和node2 不存在祖孙关系并且均落于该树的其中一棵子树上，假设均落于右子树上，则右子树的子树中必定存在这么一棵子树满足上面(c)条件，这棵子树返回值是头节点，也就是最低公共祖先节点，那么右子树最终返回的值也是该最低公共节点。左子树满足(a)条件，返回 null。故该树往上返回的值是最低公共祖先节点。

通过上面的刨析，就能写出下面优美的代码了。

public static Node lowestCommonAncestor(Node head, Node node1, Node node2) {
    if (head == null || head == node1 || head == node2) { //base case
        return head;
    }
    Node left = lowestCommonAncestor(head.left, node1, node2);
    Node right = lowestCommonAncestor(head.right, node1, node2);
    if (left != null && right != null) {
        return head;
    }
    return left != null ? left : right;
}