倍增/Tarjan解决最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

由于二叉树本身就是递归定义的，所以二叉树大部分问题都可以使用递归求解，最近公共祖先 也不例外。

对于二叉树中任意节点 $k$ ，如果出现以下情景之一， $k$ 为 $p$ 和 $q$ 的最近公共祖先

节点 $p$ 和 $q$ 其中一个节点位于 $k$ 的左子树，另外一个节点位于 $k$ 的右子树。
节点 $p$ 和 $q$ 其中一个节点为 $k$ 自己，另外一个节点位于 $k$ 的左子树或者右子树。

我们可以定义一个函数 find(TreeNode root, TreeNode p, TreeNode q) 在根节点为 root 的二叉树中查找节点 $p$ / $q$ ，该函数递归首先在子树中进行查找，这样就可以判断节点 $p$ / $q$ 是否位于子树，子树递归结束后，再根据根节点以及子树查找结果识别如上两种场景是否满足之一，如果是，这该树根节点即为 $lca(p,q)$ ，这种方法实质上还是二叉树的后序遍历。

代码如下

TreeNode lca = null;

// 在根节点为 root 的二叉树中查找节点 p 和 q, 如果找到任意一个节点, 返回 true
boolean find(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return false;
    }
    
    boolean foundOnLeft = find(root.left, p, q); // 递归在左子树中查找
    boolean foundOnRight = find(root.right, p, q); // 递归再右子树中查找
    boolean foundAny = foundOnLeft || foundOnRight; // 在子树中是否找到 p/q
    
    if (foundOnLeft && foundOnRight // ① 一个节点位于左子树，另外一个节点位于右子树
            || root == p && foundAny // ② root 为 p, 并在子树中找到 q
            || root == q && foundAny) { // ③ root 为 q, 并在子树中找到 p
        lca = root;  // 记录 lca
    }
    // 根节点为 p/q, 或者在子树中找到 p/q, 那么 p/q 就位于节点为 root 的二叉树中
    return root == p || root == q || foundAny; 
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    find(root, p, q);
    return lca;
}

该算法 时间复杂度 为 $O(n)$ ，最坏情况下，需要递归遍历树的所有节点。

如果知道了每个节点父节点的话，节点 $p$ / $q$ 可以同时沿着父节点一步一步向 $lca(p,q)$ "爬"，但是这两个节点到 $lca(p,q)$ 距离可能不一样，不一定会在 $lca(p,q)$ 相遇呀？

如下图，节点 $p$ 到 $lca(p,q)$ ( 9 → 7 → 4 → 2 ) 距离为 $3$ ，节点 $q$ 到 $lca(p,q)$ ( 5 → 2 ) 距离为 $1$ 。

CLA1.001.png

该问题可以转化为相交链表。

LCA2.001.png

为了使节点 p / q 在 lca(p,q) 相遇，需要他们到达 lca(p,q) 时走过的步数相同。为了达到这个目的，我们可以在 p / q 到达根节点后，跳到对方最开始位置再往上“爬”，这样便能使这两个节点最终在 lca(p,q) 相遇。

如上图中 p / q ，它们在相遇前

节点 p 走过路程为 $L_1+L_3+L_2$ ，即 9 → 7 → 4 → 2 → 1 → 5 → 2 。

节点 1 走过路程为 $L_2+L_3+L_1$ ，即 5 → 2 → 1 → 9 → 7 → 4 → 2 。

二叉树的最近公共祖先 III 题目中，每个节点父节点已存储，便可使用该方法


/*
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

public Node lowestCommonAncestor(Node p, Node q) {
    Node u = p, v = q;  
    while (u != v) {
        // 一步一步向上“爬”, 到达根节点后, 跳到对方最开始位置
        u = u.parent != null ? u.parent : q; 
        v = v.parent != null ? v.parent : p;
    }
    // 最终在 lca(p,q) 相遇。
    return u; 
}

另外，如果像二叉树的最近公共祖先没有存储每个节点父节点情况下，我们可以通过一次遍历求出每个节点父节点后，再使用该方法。

该算法 时间复杂度 为 $O(n)$ ，最坏情况下，需要递归遍历树的所有节点，例如树中每个节点都只有一棵子树， $p$ / $q$ 分别位于根节点和叶节点。如果需要遍历求父节点，遍历时间复杂度也为 $O(n)$ ，不影响总时间复杂度。

为了解决节点 $p$ / $q$ 到 $lca(p,q)$ 距离不一样问题，还有另外一种方法 —— 提前将二者较深者提升到和另一节点同一深度。

如下图，节点 $p$ / $q$ 分别位于 $10$ 和 $8$ ，为了使二者深度相同，先让接点 $p$ 向上“爬” 到节点和节点 $8$ 同深度的节点 $7$ ( 10 → 9 → 7 )，然后 $p$ / $q$ 再同时向上“爬”，直至它们相遇，相遇节点即为它们的最近公共祖先。

该方法前提是，每个节点 父节点 和深度已知。同样，在求 $lca(p,q)$ 前先对二叉树进行预处理 —— 通过一次遍历求出每个节点 父节点 和深度。

代码如下

public Map<TreeNode, Integer> depth = new HashMap<>(); // 父节点, 根节点的父节点为null
public Map<TreeNode, TreeNode> fa = new HashMap<>(); // 深度, 根节点深度为1

// ① 预处理, 先序遍历求每个节点父节点和深度
public void dfs(TreeNode root, int level, TreeNode parent) {  
    if (root == null) {
        return;
    }
    depth.put(root, level);
    fa.put(root, parent);

    dfs(root.left, level + 1, root);
    dfs(root.right, level + 1, root);
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    dfs(root, 1, null);
    // 保证节点 p 深度 ≥ 节点 q 深度
    if (depth.get(p) < depth.get(q)) { 
        TreeNode t = p;
        p = q;
        q = t;
    }
    int diff = depth.get(p) - depth.get(q);
    for (int i = 0; i < diff; i++) { // ② 将 p/q 提升到同一深度
        p = fa.get(p);
    }
    while (p.val != q.val) { // ③ 同时向上“爬”, 直至相遇
        p = fa.get(p);
        q = fa.get(q);
    }
    // 相遇节点即为 lca(p,q)
    return p; 
}

该算法 时间复杂度 也为 $O(n)$ 。

可以看出，上面有两个向上“爬”过程，

节点 $p$ / $q$ 较深者向上“爬”到和另外一个节点深度相同。
节点 $p$ / $q$ 一起向上“爬”，直至在 $lca(p,q)$ 相遇。

这两个过程爬行速度是比较保守的，都是沿着父节点一步一个脚印向上爬，时间复杂度为线性 $O(n)$ ，下面打算用倍增思想给这两个过程提提速。

提速最简单粗暴方法是这两个向上“爬”过程都“一步到位”，这样是否可行呢？

过程一让 $p$ / $q$ 较深者一步“爬”到和另外一个节点深度相同，确切地讲是可行的，但是需要计算每个节点不同距离的祖先节点，时间复杂度为 $O(n^2)$ ，得不偿失。

过程二 $p$ / $q$ 一步向上“爬”至 $lca(p,q)$ ，是无法实现的，因为 $lca(p,q)$ 是未知且需要求的。

综上，让这两个向上“爬”过程都“一步到位”是不可行的。

我们知道，任何十进制整数都可以完全转换为二进制，这为我们提速提供了一个新方向 —— 我们每一步只向上“爬”二的幂次方距离，“爬”行总步数为总距离二进制表示中 “1” 的位数。例如，假设过程一中， $p$ / $q$ 深度之差为 $124=2^6+2^5+2^4$ ，那么二者较深者只需向上爬三步，这三步步长分别为 $2^6$ / $2^5$ / $2^4$ ，将“爬”行时间复杂度降为 $O(lgn)$ 。

下图展示了， p / q 二者深度相差 7 时，过程一向上“爬”示意图

所以需要将这两个向上“爬”行过程总距离转换为二进制，但是，过程二中向上“爬”行总距离未知，这怎么转？

十进制转换二进制可以使用 除二取余倒读数 等方式进行转换，但在范围已经确定情况下，我们可以先求出该范围最大二的幂次方，然后从大到小罗列出所有二的幂次方，依次看十进制数是否小于等于该幂次方，如果是，则该十进制这包含该幂次方。

例如，下图展示了将 $124$ 转换为二进制过程。

过程二虽然向上“爬”行总距离未知，但是向上“爬”行总距离范围肯定不会超过二者深度较小者。另外，对于距离范围内的每个从大到小排列二的幂次方步长，可以试“爬”，如果“爬”了这步相遇了，则不能“爬”该步，最后可以使过程二 $lca(p,q)$ 。

但是这种解法会面临两个难题

提前预处理，求出每个节点所有步长为二的幂次方 $2^k$ 祖先节点。
计算 $\lfloor log_2^i\rfloor$ ，会在两个地方需要计算该值，第一个地方是上面第一个难题中，确定 $k$ 上界。如果节点深度为 $n$ ，那么根节点到该节点有 $n-1$ 步，二的幂次方步长中最长的一步步长应该是二的 $\lfloor log_2^{n-1}\rfloor$ 次方，即需要计算步长为 $[2^0, 2^{\lfloor log_2^{n-1}\rfloor}]$ 这些步的祖先节点。另外一个地方是，在过程一和过程二中，试二的幂次方步长“爬”时，得知道最长步长是多少，例如如果过程一 $p$ / $q$ 二者深度之差绝对值为 $diff$ ，那么首先应该试步长为 $2^{\lfloor log_2^{diff}\rfloor}$ 这一步。

其实上面第二个问题在 Java 中不算什么难题，Java 核心类库提供了 Math.log(i) 用于计算 $log_e^i$ ，如果要计算 $\lfloor log_2^i\rfloor$ 我们可以用换底公式 $log_2^i = \frac{log_e^i}{log_e^2}$ 求，然后再将结果强转为 int 实现取下限，即

public int lg(int i){
    return (int)(Math.log(i)/Math.log(2));  // 换底
}

但是，如果对于没有提供该方法的语言，可能计算 $\lfloor log_2^i\rfloor$ 比较困难，这里介绍一种递推算法预处理求出 $[\lfloor log_2^1\rfloor, \lfloor log_2^n\rfloor]$ 。

怎么通过 $\lfloor log_2^{k-1}\rfloor$ 推出 $\lfloor log_2^k\rfloor$ 呢？观察 $\lfloor log_2^i\rfloor$ 规律

lg.001.png

从上面表格可以看出，如果 $k$ 不是二的幂次方，那么 $\lfloor log_2^k\rfloor = \lfloor log_2^{k-1}\rfloor$ ，否则 $\lfloor log_2^k\rfloor = \lfloor log_2^{k-1}\rfloor + 1$ ，而如果 $k$ 是二的幂次方，那么 $k$ 只能是二的 $\lfloor log_2^{k-1}\rfloor+1$ 次方，我们可以用位运算快速判断。参考如下代码

int[] lg;
public void rec(int n) {
    lg = new int[n+1];
    lg[1] = 0;
    for (int i = 2; i <= n; i++) {
        lg[i] = 1 << lg[i - 1] + 1 == i ? lg[i - 1] + 1 : lg[i - 1];
    }
}

问题一其实我们也可以用递推求，我们用先序遍历访问每个节点，这里的访问操作是求节点所有步长为二的幂次方 $2^k$ 祖先节点。因为是先序遍历，在访问到节点 $r$ 时， $r$ 的所有祖先节点的步长为二的幂次方祖先节点都已经计算完成。

那对于节点 $r$ ，步长为 $2^k$ 的祖先节点怎么通过步长为 $2^{k-1}$ 的祖先节点推导出来呢？

我们可以将步长为 $2^k$ 这一步分解为两步 $2^{k-1} + 2^{k-1}$ ，因为从前往后推，所以步长为 $2^{k-1}$ 的祖先节点已知，我们先“爬”到长为 $2^{k-1}$ 的祖先节点，再从该节点向上“爬”步长为 $2^{k-1}$ 一步（因为先序遍历该节点所有步长为二的你幂方祖先节点都已经求出）即可以到达与 $r$ 节点相距 $2^k$ 的祖先节点。

如下图

我们在求节点 $9$ 步长为 $2^3$ 祖先节点时，可以将其拆解为 $2^2$ / $2^2$ 两步。

最后倍增代码参考如下


// key:节点 ⟶ value:节点深度, 根节点深底为 1
public Map<TreeNode, Integer> depth = new HashMap<>();

// key:节点 r ⟶ { key: i ⟶ value:与节点 r 相距 2^i 的祖先节点 }
public Map<TreeNode, Map<Integer, TreeNode>> fa = new HashMap<>();

public int lg(int i) {
    return (int) (Math.log(i) / Math.log(2));  // 换底
}

public void preorderTraverse(TreeNode r, TreeNode p) {  // p为r父亲节点

    if (r == null) {  // 空树, 递归结束
        return;
    }

    // ① 访问根节点
    // 根节点第 1 层, 非根节点为父亲节点层册加一
    int level = p == null ? 1 : depth.get(p) + 1; // 计算节点 r 层次
    depth.put(r, level);

    Map<Integer, TreeNode> map = fa.computeIfAbsent(r, k -> new HashMap<>());
    map.put(0, p);  // 直接父亲节点, 即相距 2^0 祖先节点

    int max = lg(level - 1); // 最长步
    for (int i = 1; i <= max; i++) { // 递推
        map.put(i, fa.get(map.get(i - 1)).get(i - 1));
    }

    preorderTraverse(r.left, r);  // ② 递归左子树
    preorderTraverse(r.right, r); // ③ 递归右子树

}

public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {

    preorderTraverse(root, null);  // 预处理

    int diff = depth.get(p) - depth.get(q);  // 计算 p/q 深度差
    if (diff < 0) {
        TreeNode t = p;
        p = q;
        q = t;
    }
    diff = Math.abs(diff);

    if (diff != 0) {
        int max = lg(diff);
        for (int i = max; i >= 0; i--) {   // 过程一, p向上"爬"到和q同一深度
            if (diff >= 1 << i) { // 深度差够, 则向上"爬"
                diff -= 1 << i;
                p = fa.get(p).get(i);
            }
        }
    }
    if (p == q) {
        return p;
    }
    int max = lg(depth.get(p) - 1);
    for (int i = max; i >= 0; i--) {  // 过程二, p/q "爬"完 lca(p, q) 前所有距离
        if (fa.get(p).get(i) != fa.get(q).get(i)) {  // 不相遇, 则向上"爬"
            p = fa.get(p).get(i);
            q = fa.get(q).get(i);

        }
    }
    return fa.get(q).get(0);  // 向上一步是 lca(p, q)
}

我们计算下该算法时间复杂度，首先预处理函数 preorderTraverse(TreeNode r, TreeNode p) 先序遍历到每个节点，时间复杂度为 $O(n)$ ，其中 $n$ 为节点数量，然后访问每个节点 $r$ ，求 $r$ 所有步长为二的幂次方祖先节点时间复杂度为 $log_2^n$ ，所以预处理函数总时间复杂度为 $O(nlogn)$ 。另外过程一，将 $p$ / $q$ 较深者提升至同一深度时间复杂度为 $log_2^n$ ，过程二时间复杂度也为 $log_2^n$ ，故总时间复杂度为 $O(nlogn)$ 。

会发现这比我们之前朴素算法时间复杂度 $O(n)$ 还要高，这咋越优化时间复杂度越高呢？

其实，对于倍增求 $lca$ 要区分使用场景，该算法主要用在 多次询问 情况下，即要求多组 $p$ / $q$ 的 $lca$ 。假设 $m$ 次询问，如果朴素算法需要循环 $m$ 次，总时间复杂度为 $O(mn)$ ，但是对于倍增算法，预处理只需要处理一次，时间复杂度还是 $O(nlogn)$ ，后面求 $m$ 次询问 $lca$ 时间复杂度为 $mlogn$ ，总时间复杂度为 $O(max(nlogn, mlogn))$ ，如果询问次数 $m$ 越大，倍增算法时间复杂度优势越明显。

例如，当给定一个节点，求该节点和其余所有节点 $lca$ 时， $m=n-1$ ，朴素算法时间复杂度为 $O(n^2)$ ，而倍增算法时间复杂度为 $O(nlogn)$ 。

对于多次询问求 $lca$ 还有其他算法，这里介绍一种离线算法 —— Tarjan 。

该算法以其作者 Robert Tarjan 命名。 Tarjan 是一位极其杰出的计算机科学家，也是1986年图灵奖得主，他发明不少算法，其中比较闻名的除了本节解决 $lca$ 问题外，还有后面我们要接触到的强连通分量问题等，这些算法都以他的名字命名，所以有时会让人混淆这几种算法。另外，Tarjan 还参与了开发斐波那契堆、伸展树，分析并查集的工作。

这里首先需要知道什么是 离线算法。

离线算法是指在 执行算法前需要已知所有询问输入 。

这就意味着需要存储所有询问，如果询问次数特别大就可能内存受限。

与其相对应的是 在线算法，例如，上面倍增算求 $lca$ 就是在线算法，因为该算法不需要提前输入所有询问，而可以每输入一组询问，即可执行算法求出 $lca$ 并将结果输出。

Tarjan 算法没有上面倍增算法复杂，该算法通过二叉树的一次遍历，求出所有询问的 $lca$ 。即对于询问 $lca(p, q)$ ，在访问节点 $q$ 时，如果节点 $p$ 已经访问过，那么即可求出 $lca(p, q)$ ，反之亦然。

假设，先序遍历二叉树，当前访问节点为 $v$ ，且节点 $u$ 已经访问过，看下 Tarjan 算法如果求一次询问中 $lca(u, v)$ 。

这种情况下， $lca(u, v)$ 肯定是节点 $v$ 的祖先节点，所以我们只需要沿着 $v$ 的祖先链向上检查这些祖先节点，如果该祖先节点子树（包含该祖先节点）已经访问节点中首先出现节点 u，那么即可确定该节点为 $lca(u, v)$ 。

tarjan.001.png

如下图，如果先序遍历当前访问节点 $v$ 为节点 $13$ ，且节点 $u$ 已经访问过，那么 $lca(u, v)$ 只能是节点 $9$ / $5$ / $2$ / $1$ ，沿着祖先链 $9 → 5 → 2 → 1$ 找，看那个祖先节点子树（包含该祖先节点）已经访问节点中首先出现节点 $u$ 。例如，如果 $u = 9$ ，那么，沿着祖先链 $9 → 5 → 2 → 1$ 找节点 $9$ 就停止，即 $lca(u, v)=9$ 。如果 $u = 11$ ，那么，沿着祖先链 $9 → 5 → 2 → 1$ 找节点 $5$ 就停止，即 $lca(u, v)=5$ 。

UnionFind<TreeNode> unionFind = new UnionFind<>(Collections.emptySet());
Map<TreeNode, TreeNode> fa = new HashMap<>();
Set<TreeNode> visited = new HashSet<>();
Map<TreeNode, List<TreeNode>> query = new HashMap<>();


public void tarjan(TreeNode r) {
   visited.add(r);
   unionFind.addElement(r);
   fa.put(r, r);
   List<TreeNode> list = Arrays.asList(r.left, r.right);
   for (TreeNode child : list) {
       if (child != null) {
           tarjan(child);
           unionFind.union(r, child);
           fa.put(unionFind.find(r), r);
       }

   }
   if (query.get(r) != null) {
       for (TreeNode node : query.get(r)) {
           if (visited.contains(node)) {
               System.out.println("lca(" + r.val + "," + node.val + ") =" + fa.get(unionFind.find(node)).val);
           }
       }
   }
}