二叉树的最近公共祖先

GitHub undefined undefined undefined

培养框架思维,真正爱上算法!关注公众号查看更新文章👆

相关推荐:

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

236.二叉树的最近公共祖先(中等)


如果说笔试的时候喜欢考各种动归回溯的骚操作,面试其实最喜欢考比较经典的问题,难度不算太大,而且也比较实用。

上篇文章 四个命令玩转 Git 写了 Git 最常用的命令,没有提分支合并,其实分支合并没什么困难的,主要就是 mergerebase 两种方式。本文就用 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 节点开始,重演 LCAdev 几个 commit 的修改,如果这些修改和 LCAmastercommit 有冲突,就会提示你手动解决冲突,最后的结果就是把 dev 的分支完全接到 master 上面。

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

_____________

本文只能在 labuladong 公众号查看,关注后可直接搜索本站内容:

Copyright © labuladong 2020 all right reserved,powered by Gitbook该文件修订时间: 2021-04-19 18:19:18

results matching ""

    No results matching ""