×

由于本站访问压力较大
微信扫码关注公众号 labuladong
回复关键词「解锁
按照操作即可解锁本站全部文章

公众号

Git原理之最近公共祖先

通知: 数据结构精品课 已更新到 V1.9,点击这里体验 刷题全家桶

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

牛客 LeetCode 力扣 难度
- 1644. Lowest Common Ancestor of a Binary Tree II🔒 1644. 二叉树的最近公共祖先 II🔒 🟠
- 1650. Lowest Common Ancestor of a Binary Tree III🔒 1650. 二叉树的最近公共祖先 III🔒 🟠
- 1676. Lowest Common Ancestor of a Binary Tree IV🔒 1676. 二叉树的最近公共祖先 IV🔒 🟠
- 235. Lowest Common Ancestor of a Binary Search Tree 235. 二叉搜索树的最近公共祖先 🟢
- 236. Lowest Common Ancestor of a Binary Tree 236. 二叉树的最近公共祖先 🟠
- - 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 🟢
- - 剑指 Offer 68 - II. 二叉树的最近公共祖先 🟢

———–

PS: 刷题插件 集成了手把手刷二叉树功能,按照公式和套路讲解了 150 道二叉树题目,可手把手带你刷完二叉树分类的题目,迅速掌握递归思维。

如果说笔试的时候经常遇到各种动归回溯的骚操作,那么面试会倾向于一些比较经典的问题,难度不算大,而且也比较实用。

本文就用 Git 引出一个经典的算法问题:最近公共祖先(Lowest Common Ancestor,简称 LCA)。

git pull 这个命令我们经常会用,它默认是使用 merge 方式将远端别人的修改拉到本地;如果带上参数 git pull -r,就会使用 rebase 的方式将远端修改拉到本地。

这二者最直观的区别就是:merge 方式合并的分支会看到很多「分叉」,而 rebase 方式合并的分支就是一条直线。但无论哪种方式,如果存在冲突,Git 都会检测出来并让你手动解决冲突。

那么问题来了,Git 是如何检测两条分支是否存在冲突的呢?

rebase 命令为例,比如下图的情况,我站在 dev 分支执行 git rebase master,然后 dev 就会接到 master 分支之上:

这个过程中,Git 是这么做的:

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

那么,Git 是如何找到两条不同分支的最近公共祖先的呢?这就是一个经典的算法问题了,下面我来由浅入深讲一讲。

_____________

应合作方要求,本文不便在此发布,请扫码关注回复关键词「lca」或 点这里 查看:

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释