https://labuladong.gitee.io/algo/2/18/30/
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
———–
如果说笔试的时候喜欢考各种动归回溯的骚操作，面试其实最喜欢考比较经典的问题，难度不算太大，而且也比较实用。
上篇文章 四个命令玩转 Git 写了 Git 最常用的命令，没有提分支合并，其实分支合并没什么困难的，主要就是 merge 和 rebase 两种方式。本文就用 Git 的 rebase 工作方式引出一个经典的算法问题：最近公共祖先（Lowest Common Ancestor，简称 LCA）。
比如 git pull 这个命令，我们经常会用，它默认是使用 merge 方式将远端别人的修改拉到本地；如果带上参数 git pull -r，就会使用 rebase 的方式将远端修改拉到本地。
这二者最直观的区别就是：merge 方式合并的分支会有很多「分叉」，而 rebase 方式合并的分支就是一条直线。
对于多人协作，merge 方式并不好，举例来说，之前有很多朋友参加了在 GitHub 上的仓库翻译工作，GitHub 的 Pull Request 功能是使用 merge 方式，所以你看 fucking-algorithm 仓库的 Git 历史：
画面看起来很炫酷，但实际上我们并不希望出现这种情形的。你想想，光是合并别人的代码就这般群魔乱舞，如果说你本地还有多个开发分支，那画面肯定更杂乱，杂乱就意味着很容易出问题，所以一般来说，实际工作中更推荐使用 rebase 方式合并代码。
那么问题来了，rebase 是如何将两条不同的分支合并到同一条分支的呢：
上图的情况是，我站在 dev 分支，使用 git rebase master，然后就会把 dev 接到 master 分支之上。Git 是这么做的：
首先，找到这两条分支的最近公共祖先 LCA，然后从 master 节点开始，重演 LCA 到 dev 几个 commit 的修改，如果这些修改和 LCA 到 master 的 commit 有冲突，就会提示你手动解决冲突，最后的结果就是把 dev 的分支完全接到 master 上面。
那么，Git 是如何找到两条不同分支的最近公共祖先的呢？这就是一个经典的算法问题了，下面来详解。
＿＿＿＿＿＿＿＿＿＿＿＿＿