labuladong 用 Git 来讲讲二叉树最近公共祖先

上篇文章我用四个命令，总结了 Git 的所有套路写了 Git 最常用的命令，没有提分支合并，其实分支合并没什么困难的，主要就是merge和rebase两种方式。本文就用 Git 的rebase工作方式引出一个经典的算法问题：最近公共祖先（Lowest Common Ancestor，简称 LCA）。

实际工作中更推荐使用rebase方式合并代码。

那么问题来了，rebase是如何将两条不同的分支合并到同一条分支的呢：

上图的情况是，我站在dev分支，使用git rebase master，然后就会把dev接到master分支之上。Git 是这么做的：

首先，找到这两条分支的最近公共祖先LCA，然后从master节点开始，重演LCA到dev几个commit的修改，如果这些修改和LCA到master的commit有冲突，就会提示你手动解决冲突，最后的结果就是把dev的分支完全接到master上面。

那么，Git 是如何找到两条不同分支的最近公共祖先的呢？这就是一个经典的算法问题了，下面来详解。

二叉树的最近公共祖先

这个问题可以在 LeetCode 上找到，第 236 题，看下题目：

NOTE:

原题: leetcode 236. 二叉树的最近公共祖先

函数的签名如下：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q);

root节点确定了一棵二叉树，p和q是这这棵二叉树上的两个节点，让你返回p节点和q节点的最近公共祖先节点。

我们前文学习数据结构和算法的框架思维就说过了，所有二叉树的套路都是一样的：

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

所以，只要看到二叉树的问题，先把这个框架写出来准没问题：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
}

现在我们思考如何添加一些细节，把框架改造成解法。

解法思路

第一个问题: 这个函数是干嘛的？

NOTE:

其实这一段，主要是在描述 lowestCommonAncestor这个函数的**返回值**；理解了这个函数的**返回值**，就基本上理解了这个算法，理解这函数的返回值本节的前提是需要完整地掌握解题思路的，在 "最近公共祖先"的含义"" 节中，简述了解题思路:

"后序遍历是从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个root，你说这是不是最近公共祖先"

因此:

一、需要根据左右子树中是否包含目标节点来确定当前节点root 是否是 "公共祖先"、"相交的节点"(需要"返回那个节点"，来表示p或q是否在这棵子树中，然后在上层节点，也就是它们的parent node、"相交的节点"，就可以判断):

1、如果 左子树 中包含一个目标节点且 右子树 中包含一个目标节点，显然，当前节点root就是"公共祖先"、"相交的节点"

2、如果当前节点root 不是 "公共祖先"、"相交的节点"，那么就需要返回到向上一层去，看上一层是否是"公共祖先"、"相交的节点"

二、后续遍历

仔细看后面完整的实现代码，它是典型的post-order遍历的形式:
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case
    if (root == null) return null;
    if (root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 情况 1
    if (left != null && right != null) {
        return root;
    }
    // 情况 2
    if (left == null && right == null) {
        return null;
    }
    // 情况 3
    return left == null ? right : left;
}
三、特殊条件的说明:

如果要找 2 和 8的公共祖先，看图可知，答案是 2，结合上述算法来看，它能够正确的处理这种情况。

首先看第一个问题，这个函数是干嘛的？或者说，你给我描述一下lowestCommonAncestor这个函数的「定义」吧。

描述：给该函数输入三个参数root，p，q，它会返回一个节点。

情况 1，如果p和q都在以root为根的树中，函数返回的即是p和q的最近公共祖先节点。

情况 2，如果p和q都不在以root为根的树中怎么办呢？函数理所当然地返回null呗。

情况 3，如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点。

题目说了输入的p和q一定存在于以root为根的树中，但是递归过程中，以上三种情况都有可能发生，所以说这里要定义清楚，后续这些定义都会在代码中体现。

第二个问题: 这个函数的参数中，变量是什么

然后来看第二个问题，这个函数的参数中，变量是什么？或者说，你描述一个这个函数的「状态」吧。

描述：函数参数中的变量是root，因为根据框架，lowestCommonAncestor(root)会递归调用root.left和root.right；至于p和q，我们要求它俩的**公共祖先**，它俩肯定不会变化的。

第二个问题也解决了，你也可以理解这是「状态转移」，每次递归在做什么？不就是在把「以root为根」转移成「以root的子节点为根」，不断缩小问题规模嘛？

第三个问题: 得到函数的递归结果，你该干嘛

最后来看第三个问题，得到函数的递归结果，你该干嘛？或者说，得到递归调用的结果后，你做什么「选择」？

这就像动态规划系列问题，怎么做选择，需要观察问题的性质，找规律。那么我们就得分析这个「最近公共祖先节点」有什么特点呢？刚才说了函数中的变量是root参数，所以这里都要围绕root节点的情况来展开讨论。

先想 base case，如果root为空，肯定得返回null。如果root本身就是p或者q，比如说root就是p节点吧，如果q存在于以root为根的树中，显然root就是最近公共祖先；即使q不存在于以root为根的树中，按照情况 3 的定义，也应该返回root节点。

以上两种情况的 base case 就可以把框架代码填充一点了：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 两种情况的 base case
    if (root == null) return null;
    if (root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
}

现在就要面临真正的挑战了，用递归调用的结果left和right来搞点事情。根据刚才第一个问题中对函数的定义，我们继续分情况讨论：

情况 1，如果p和q都在以root为根的树中，那么left和right一定分别是p和q（从 base case 看出来的）。

情况 2，如果p和q都不在以root为根的树中，直接返回null。

情况 3，如果p和q只有一个存在于root为根的树中，函数返回该节点。

明白了上面三点，可以直接看解法代码了：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case
    if (root == null) return null;
    if (root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 情况 1
    if (left != null && right != null) {
        return root;
    }
    // 情况 2
    if (left == null && right == null) {
        return null;
    }
    // 情况 3
    return left == null ? right : left;
}

对于情况 1，你肯定有疑问，left和right非空，分别是p和q，可以说明root是它们的公共祖先，但能确定root就是「最近」公共祖先吗？

"最近公共祖先"的含义

这就是一个巧妙的地方了，因为这里是二叉树的后序遍历啊！前序遍历可以理解为是从上往下，而后序遍历是从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个root，你说这是不是最近公共祖先呢？

综上，二叉树的最近公共祖先就计算出来了。