发表Dev1 小时读完 (大约8955个字)

浅谈Git的应用

浅谈Git的应用

info

INFO

本文内容含有较多的引用，笔者会标注本文中所有引用内容，并在引文末尾使用脚注注明引文出处．
受引用来源的限制，本文将采取较为复杂的许可．

引文部分已全部标注．
笔者尊重所有创作者的知识产权，希望能以合理的方式引用他人的作品，但因笔者的法律知识有限，在操作中可能出现疏忽和错误，如有任何建议，请在文章末尾的评论区中评论．在此也感谢本文的引文的作者．

写在前面的话：笔者写这篇文章并非为了教会读者Git的详细用法，而是为了告诉读者们Git能满足什么需求．笔者期望阅读本文的读者在某一天出现有关版本控制的需求时，能想起曾在某个不知名的博客中看到过Git有个功能可以解决当前遇到的问题．与其说本文在介绍Git的使用方式，不如说本文在介绍Git已有的部分常用功能．至于有意详细的学习Git的用法的读者，本文无法满足你的需求，笔者建议阅读Git Pro Book来满足你的需求．

为什么需要版本控制

你是否曾为误删重要文件而懊悔，你是否曾为数据丢失而苦恼？你是否曾错误改动文件而无法更正？

你丢失的或许是几日的心血，或许是照片中美好的回忆．但对于一个项目而言，任何文件的丢失与错误的修改都可能是致命．

版本控制就如同游戏中的存档，是开发中的后悔药．

我想有的人曾因担心之后的操作把已有的工作搞砸，提前复制或者备份一份已有的文件，然后再进行不太确定的操作．
很多软件为用户提供了撤销的功能，从某种层面上说，这也是一种版本控制，你能想象如Word、PowerPoint、PhotoShop等大型软件不提供撤销功能会造成多么大的不便吗？

当然，版本控制也绝非一个撤销键这样简单．

tip
小故事

客人来到餐厅用餐．
客人：来一份宫保鸡丁
你：这好办．
进入后厨，完成客户的需求中…
客人：孩子喜欢吃牛肉，麻烦你把鸡丁换成牛肉
你：不放鸡丁放牛肉还是宫保鸡丁吗？您确定要这样吗？
客人：这很难吗？无非是把鸡丁换成牛肉，别的该怎么做还是怎么做，这很难吗．
你：好吧．

此时，你默默的从锅中挑出即将炒熟的鸡丁，换成牛肉丁

客人：你怎么这么慢？要不算了，还是放鸡丁吧？我都要饿死了，怎么快怎么来？！
你：……

此时，你默默从锅中挑出即将炒熟的牛肉丁，把鸡丁放回去

据说这很像程序员们遇到的犹豫不定的客户，频繁的改动需求导致项目反复改动．

虽然版本控制无助于开发新的功能，但在使用了版本控制之后，至少在客户改动需求又反悔时，版本控制能让开发者快速的投入新的开发工作，而不是花费大量精力把已有的改动还原回去（当然，这只是使用版本控制的好处之一）．

通常来说，大多数软件提供的撤销功能是有很多不足的．

  • 无法直接撤销至任意一步，只能逐步撤销
  • 无法撤销至这次打开软件之前的版本，撤销的步数受限
  • 不能保存撤销和重做的记录
  • 撤销后的修改会影响撤销，无法保留现有修改的同时撤销过去的修改

当然，会有聪明的人说：「何必这么麻烦，我提前复制一份就好．」

不可否认，这通常是一个有效的做法，但也会带来一些麻烦．

一个1MB左右的文件通过复制备份10个版本也才10MB．但1GB的文件通过复制的方式备份10份就要10GB了．

danger
WARNING
虽然笔者用备份作为说明版本控制的一个例子，版本控制在某种程度上来说具有备份的作用，备份在某种程度上来说也实现了版本控制，但这也只是说明两者的作用有交集，切不可混为一谈．笔者此处使用这种说法只是为了帮助对版本控制感到陌生的读者理解版本控制的部分作用，请原谅笔者这种不太严谨的做法．

通过复制备份原文件，手动完成版本控制，在文件大小近似不变的情况下，所需要的空间和复制次数具有线性相关关系，长期依靠复制完成版本控制不是一个好的办法．

secondary
INFO

截至 2020-12-03 03:13：08 ，Linux 内核源码树（Linux kernel source tree）有968,247 次提交（commits），在Github上仅存储了2.94GB的数据．

https://github.com/torvalds/linux

在多人协作的时候，使用版本控制系统具有更多的优势．

  • 保留了每次修改的结果，方便的对比查看不同版本之间的差异
  • 方便的查看他人修改了什么内容
  • 方便的查看文件内容的修改者
  • 允许对所有参与者划分权限，禁止部分人修改部分重要内容
  • 进行代码审核(Code Review)

在网络上，用户能方便的下载同一个软件的不同版本，以Google Chrome为例，在Chrome官网上有Chrome、Chrome Dev、Chrome Canary这些不同的版本．

Chrome
Chrome Dev
Chrome Canary

将同一个软件根据稳定性和需求分成不同版本提供给不同的群体是十分常见的现象．但在chromium的源码仓库却会发现Google并非把Chrome、Chrome Dev、Chrome Canary当作三个程序来维护，而是通过使用版本控制轻松的避免了提供三个版本的软件所带来的麻烦，这一切都是这样的理所当然．

为什么选择Git

  • Git 是基于GPLv2的自由软件(free software)（Git 的部分内容不是基于GPLv2的，但是也基于一个与GPLv2兼容的协议），Git是软件自由保护组织(Software Freedom Conservancy)的子项目
  • Git 是Linus Torvalds为维护Linux Kernel设计的工具

Git本就是为程序开发设计的版本控制系统，比其他的版本控制系统更适合程序开发的需求

除此之外，Git 还拥有这些特点

  • 速度
  • 简单的设计
  • 对非线性开发模式的强力支持（允许成千上万个并行开发的分支）
  • 完全分布式
  • 有能力高效管理类似 Linux 内核一样的超大规模项目（速度和数据量）

Git 日臻成熟完善，在高度易用的同时，仍然保留着初期设定的目标．
它的速度飞快，极其适合管理大项目，有着令人难以置信的非线性分支管理系统[2]

Software Freedom Conservancy的更多信息> 软件自由保护组织（Software Freedom Conservancy，简称SFC）是一个旨在为自由开源软件项目提供支持和基础设施的非营利组织，成立于2006年． [1]

Git 的历史

Linux 内核开源项目有着为数众多的参与者． 绝大多数的 Linux 内核维护工作都花在了提交补丁和保存归档的繁琐事务上（1991－2002年间）．到 2002 年，整个项目组开始启用一个专有的分布式版本控制系统 BitKeeper 来管理和维护代码．[2]

因为BitKeeper为专有软件，这个决定在社区中长期遭受质疑．在Linux社区中，特别是理查德·斯托曼与自由软件基金会的成员，主张应该使用开放源代码的软件来作为Linux内核的版本控制系统．林纳斯·托瓦兹曾考虑过采用现成软件作为版本控制系统（例如Monotone），但这些软件都存在一些问题，特别是性能不佳．现成的方案，如CVS的架构，受到林纳斯·托瓦兹的批评．[3]

info

INFO

补充资料1

FSF 遵循这样的规则：我们不能在自己的计算机上安装任何专有软件，除非暂时性地用于一种特定用途，即编写一个自由软件来取代它．除此之外，我们感觉没有任何可能的借口来安装一款专有软件．

例如，在 20 世纪 80 年代，我们认为在我们的计算机上安装 Unix 是合理的，由于我们需要用它编写一个可以取代 Unix 的自由操作系统．而现在，由于自由的操作系统已经有了，因此这一借口不再适用；我们不会使用任何专有操作系统，并且我们所组装的任何一台新计算机都必须运行一款完全自由的操作系统．[4]

补充资料2

Bitkeeper议题
（参看下面的最后更新．）

使用Bitkeeper作为Linux源码的储存工具对于自由软件社区具有重大的影响，因为任何想要密切追踪Linux修定版本的人只能安装该非自由软件才行．肯定至少有数十或甚至数百名的内核黑客已经这么做了．他们之中大部份的人已经渐渐地说服了自己使用非自由软件是没有关系的，以避免在自己电脑上装有Bitkeeper带来的认知冲突造成的不良感觉．对此我们可以做些什么呢？

一个解决方式是为Linux源码设定另一个储存库，使用CVS或其他自由的版本控制系统，并设置新版本自动加载．这样可以使用Bitkeeper来对最新的版本进行存取，然后再将新的版本安装到CVS中．这种更新操作可以自动且频繁地运行．

自由软件基金会不能这样做，因为我们不能在我们的机器上安装Bitkeeper．我们的机器上现在没有非自由的系统或应用程序，而且我们的原则也是必须维持这种方式．运行Bitkeeper储存工具的操作需要某个愿意将Bitkeeper安装在他的机器上的人，除非有人可以找出或做出一个使用自由软件来运作的方式．

Linux源码本身有着更严重的问题：它们实际上包含一些非自由软件．相当多的设备驱动程序包含了代表固件程序的数组，它们会被安装在这些装置内．这些程序不是自由软件．在设备寄存器写入的数据是一件事；大量二进制代码是另外一回事．

在Linux“源码”文件中出现的这些只有二进制形式的程序，造成了另一个问题：那就是，Linux的二进制码到底是否可以合法地再发布．GPL要求“完备的相关源码”，而数字字符串并非源码．按照相同理由，添加这样的二进制码到Linux源码违反了GPL的规定．

Linux开发者有个项目是将这些固件程序转移到单独的文件中；该项目需要数年的时间才会成熟，不过当其完成时将会解决这个问题；我们可以作出一个“自由的Linux”版本，而其中不包括任何非自由的固件程序．但是如果大多数人都在使用非自由的“官方”Linux版本，那么该项目本身并没有什么用处．这很有可能发生，因为自由版本在许多平台上，如果没有非自由的固件都将无法运行．“自由的Linux”工程将不得不弄明白这些固件究竟做些什么，并且为它之编写源码，也许要以汇编语言为要运行的嵌入式处理器平台来撰写．这将会是件极其艰巨的工作．但是如果我们在早几年就开始一点一滴地进行，而不是等它堆积起来，它就不那么艰巨了．通过招募人员来进行这项工作，我们将不得不克服由某些Linux开发者所散播的“这件工作是不必要的”观念．

作为内核的Linux通常被视为自由软件的旗舰，然而它目前的版本却有一部份是非自由的．为什么会这样？就像决定使用Bitkeeper的问题一样，这个问题反应出了Linux原始开发者的态度，就是认为“技术上更好”比自由更重要．

历史告诉我们：珍惜你的自由，否则你将会失去它．以“不要以政治来烦我们”作为回应的人，是那些不愿接受教训的人．

最后更新：从2005年起，Linux内核的源代码不再使用BitKeeper管理．参看文章，致谢Larry McVoy．Linux源代码仍然含有非自由的固件blobs，但是在2008年1月，我们维护了一个自由版的Linux，并被自由的GNU/Linux发行版使用．[5]

Free Software Foundation的更多信息>「自由软件基金会（FSF）是一个非盈利组织．我们的使命是在全球范围内促进计算机用户的自由．我们捍卫所有软件用户的权利．」[6]

生活在当今的人们可能难以体会自由软件运动中对软件自由的向往和追求．即使在当时，也有很多人自由软件运动中追求的自由表示不解与不懈，但笔者身为GNU/Linux与Git的使用者和受益者，凭借自己对Open Free Share的些许感悟对他们曾经作出的一切表示挚诚的感谢和深深的敬意．

2005年，安德鲁·垂鸠写了一个简单程序，可以连接BitKeeper的存储库，BitKeeper著作权拥有者拉里·麦沃伊认为安德鲁·垂鸠对BitKeeper内部使用的协议进行逆向工程，决定收回无偿使用BitKeeper的许可．Linux内核开发团队与BitMover公司进行磋商，但无法解决他们之间的歧见．林纳斯·托瓦兹决定自行开发版本控制系统替代BitKeeper，以十天的时间编写出git第一个版本．[3]

使用Git

本文不介绍如何通过图形化界面来使用Git，本文只讨论Git在终端中的使用．

Git 基础

Git项目的不同阶段[13]

Git有三种状态，你的文件可能处于其中之一：已提交（committed）、已修改（modified）和已暂存（staged）．
已修改表示修改了文件，但还没保存到数据库中．
已暂存表示对一个已修改文件的当前版本做了标记，使之包含在下次提交的快照中．
已提交表示数据已经安全地保存在本地数据库中．[13]

文件的状态变化周期[2]

  • init

为了在没有使用过Git的项目中使用Git，首先需要完成初始化Git仓库

在终端内，将工作目录切换至项目的目录，便可使用git init命令完成对Git仓库的初始化．

  • clone

任何人都可以从Github或者其他平台上获取使用Git版本控制的项目．

只需要使用git clone <url>就可以完整的获取url所对应的项目的所有源码以及所有的改动历史．

  • status

使用git status能查看git仓库的修改状态．

  • log

使用git log能查看git仓库的日志．日志中包括了很多信息．

  • diff

该命令会显示Git仓库中和上次提交相比已被修改的文件．

  • add

使用命令 git add 开始跟踪一个文件． 所以，要跟踪 README 文件，运行：

$ git add README
此时再运行 git status 命令，会看到 README 文件已被跟踪，并处于暂存状态：

$ git status
On branch master
Your branch is up-to-date with ‘origin/master’.
Changes to be committed:
(use “git restore —staged…” to unstage)

new file: README
只要在 Changes to be committed 这行下面的，就说明是已暂存状态． 如果此时提交，那么该文件在你运行 git add 时的版本将被留存在后续的历史记录中． 你可能会想起之前我们使用 git init 后就运行了 git add命令，开始跟踪当前目录下的文件． git add 命令使用文件或目录的路径作为参数；如果参数是目录的路径，该命令将递归地跟踪该目录下的所有文件．[2]

  • commit

git commit命令用来提交已经暂存的更改．

参数 -m message 附加提交信息
参数 -S 在提交中，使用GnuPG签名

Git 进阶用法

上面的那些操作只是Git的基础用法，不能发挥Git的功能的绝大部分功能．
下面笔者来介绍Git的高阶用法．

检出
  • 清空暂存区

git checkout HEAD

  • 检出至某一版本

git checkout <ref>
git checkout <commit>

1
2
3
graph LR
    C5-->C4-->C3-->C2-->C1-->C0;
    F((master))-->C4;

<ref>可以是一个分支名称，也可以是一个相对引用，下面是相对引用的语法

使用 A^ 指代 A 之前的第 1 个提交记录，如 master^ 指master的前驱，即C3
使用 A^^ 指代 A 之前的第 2 个提交记录，如 master^^ 指master的前驱的前驱，即C2
使用 A^^^ 指代 A 之前的第 3 个提交记录，如 master^^^ 指master的前驱的前驱的前驱，即C1

……

笔者相信读者们不会喜欢用A^^^^指代 A 之前的第 4 个提交记录，因为这个命令实在太长了，下面有更简单的命令

使用 A~n 指代 A 之前的 n 个提交记录，如 master~2 指master的前驱的前驱，等价于A^^，即C2；master~4 指master的前驱的前驱的前驱的前驱，等价于A^^^^，即C0．

分支管理

为什么需要分支管理？开发中常常会有突发事件，加入你正在开发新的功能，但突然发现已有的程序存在严重的bug，你不得不紧急修复它．在开发中，提交不完整的代码会对项目的其他参与者造成巨大的影响．这不是一个正确的行为．那么你该怎么办？
如果没有分支管理，你可能会将未完成的代码删除，或者回退至过去的版本，但这可是你的心血．你还有可能复制一份现在的代码作为备份，然后把代码回退至过去的版本
但有了分支管理，这些问题都消失了．

实际工作中你可能会用到类似的工作流． 你将经历如下步骤：

  1. 开发某个网站．
  2. 为实现某个新的用户需求，创建一个分支．
  3. 在这个分支上开展工作．
    正在此时，你突然接到一个电话说有个很严重的问题需要紧急修补．
    你将按照如下方式来处理：
  4. 切换到你的线上分支（production branch）．
  5. 为这个紧急任务新建一个分支，并在其中修复它．
  6. 在测试通过之后，切换回线上分支，然后合并这个修补分支，最后将改动推送到线上分支．
  7. 切换回你最初工作的分支上，继续工作．[9]
  • git branch <branch>创建新的分支
  • git checkout <branch>切换至已创建的新分支

这两条命令连续使用的情况可简化为：git checkout -b <branch> 创建并切换至新的分支

  • git branch -d <branch>删除一个分支
合并(merge)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
gitGraph:
options
{
    "nodeSpacing": 150,
    "nodeRadius": 10
}
end
commit
branch dev
checkout dev
commit
checkout master
commit
commit
merge dev
commit

如图，上图中dev分支的内容被合并至了master分支．

使用git merge <branch>可以指定的分支合并至当前分支．
Git在无冲突的情况下可以自动合并两个分支的更改．但Git并不总是能自动完成合并，当遇到合并冲突时，需要手动解决冲突才能完成合并．

变基(rebase)
1
2
3
4
5
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master))-->C3;
    G((dev))-->C5;

Git的rebase功能允许使用者修改过去的Git提交历史，也提供一种比 merge 更易理解的方式处理提交内容的合并的需求．例如上图中，通过git rebase master dev指令，Git能分析dev分支中C4和C5中的改动，并在master分支上重复这些改动，实现下图中的效果．

1
2
3
4
5
6
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    C5'-->C4'-->C3;
    F((master))-->C3;
    G((dev))-->C5';

cherry-pick

通过git cherry-pick <commit>便可将一次提交复制至HEAD所指向的位置之后．

1
2
3
4
5
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master*))-->C3;
    G((dev))-->C5;

在上图的情况中，使用git cherry-pick C4便可以将C4的提交内容复制至C3之后．实现下图中的效果．

1
2
3
4
5
graph LR
    C4'-->C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master))-->C4';
    G((dev))-->C5;

远程分支

远程引用是对远程仓库的引用（指针），包括分支、标签等等． 你可以通过 git ls-remote来显式地获得远程引用的完整列表， 或者通过 git remote show获得远程分支的更多信息． 然而，一个更常见的做法是利用远程跟踪分支．

它们以/的形式命名． 例如，如果你想要看你最后一次与远程仓库 origin 通信时 master 分支的状态，你可以查看 origin/master 分支． 你与同事合作解决一个问题并且他们推送了一个 iss53 分支，你可能有自己的本地 iss53 分支， 然而在服务器上的分支会以 origin/iss53 来表示．[10]

  • git remote add <remote>添加远程仓库
  • git fetch <remote> 从远程仓库拉取数据并更新远程分支所指向的位置，但不更新本地分支所指向的位置
  • git pull从远程仓库获取数据并与本地分支合并．等价于执行git fetch <remote>之后执行git merge <branch>
  • git push <remote> <branch>将分支推送至远程仓库
  • git checkout --track <remote>/<branch>为当前的本地分支设置上游分支
  • git push <remote> --delete <branch>删除远程分支

版本回退

本地版本回退
git reset <commit>
git reset <ref>

读者可能会感到这个命令与checkout十分相似，事实确实如此，不但命令相似，作用也是相似的．在checkout命令中，命令仅改变了HEAD所指向的位置，但在reset命令中命令还会改变HEAD所指向的分支的位置．

远程版本的回退

已经推送至远程仓库的提交并不能使用reset进行回退，如果你尝试过这样做就会发现Git会提示你，你的本地分支落后与远程分支，让你拉取远程的提交记录．拉取之后被reset的记录又被恢复了，所以不该使用reset去回退远程的分支．

git revert <commit>
git revert <ref>

正确的做法是使用使用revert功能．这个功能并不像reset那样，他会保留revert的记录和revert之前commit的记录．读者们可以理解为revert不是回退，而是把用新的提交把原来提交的内容改回去．

Git 练习

与别的技术一样，想要灵活的掌握Git的用法离不开适当的练习．在个人的开发中使用Git只是一个方面，笔者推荐完成learngitbranching上面的练习，这是学习Git的有效途径．

Git 原理

Git 存储文件的快照

Git存储文件的快照[13]

Git更像是把数据看作是对小型文件系统的一系列快照．在Git中，每当你提交更新或保存项目状态时，它基本上就会对当时的全部文件创建一个快照并保存这个快照的索引．为了效率，如果文件没有修改，Git不再重新存储该文件，而是只保留一个链接指向之前存储的文件．Git对待数据更像是一个快照流．[13]

Git 引用

如果你对仓库中从一个提交（比如 1a410e）开始往前的历史感兴趣，那么可以运行 git log 1a410e 这样的命令来显示历史，不过你需要记得 1a410e 是你查看历史的起点提交． 如果我们有一个文件来保存 SHA-1 值，而该文件有一个简单的名字， 然后用这个名字指针来替代原始的 SHA-1 值的话会更加简单．

在 Git 中，这种简单的名字被称为「引用（references，或简写为 refs）」． 你可以在 .git/refs 目录下找到这类含有 SHA-1 值的文件． 在目前的项目中，这个目录没有包含任何文件，但它包含了一个简单的目录结构：

1
2
3
4
5
$ find .git/refs
.git/refs
.git/refs/heads
.git/refs/tags
$ find .git/refs -type f

[8]

Git 的分支的本质就是：

一个指向某一系列提交之首的指针或引用[8]

最近公共祖先(LCA,Lowest Common Ancestor)

Git 在执行rabase操作时，涉及寻找两个分支的最近公共祖先的问题．

1
2
3
4
5
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master))-->C3;
    G((dev))-->C5;

例如在使用git rebase master dev 时查找C3和C5找到的最近公共祖先，才能实现下图的效果．

1
2
3
4
5
6
graph LR
    C3-->C2-->C1-->C0;
      C5-->C4-->C2;
    C5'-->C4'-->C3;
    F((master))-->C3;
    G((dev))-->C5';

请看 LeetCode-236.二叉树中的最近公共祖先 ．

实现如下：

我描述一下lowestCommonAncestor这个函数的「定义」吧．

描述：给该函数输入三个参数root，p，q，它会返回一个节点．
情况 1，如果p和q都在以root为根的树中，函数返回的即使p和q的最近公共祖先节点．
情况 2，那如果p和q都不在以root为根的树中怎么办呢？函数理所当然地返回null呗．
情况 3，那如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点．

题目说了输入的p和q一定存在于以root为根的树中，但是递归过程中，以上三种情况都有可能发生，所以说这里要定义清楚，后续这些定义都会在代码中体现．
OK，第一个问题就解决了，把这个定义记在脑子里，无论发生什么，都不要怀疑这个定义的正确性，这是我们写递归函数的基本素养．
然后来看第二个问题，这个函数的参数中，变量是什么？或者说，你描述一个这个函数的「状态」吧．
描述：函数参数中的变量是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 就可以把框架代码填充一点了：

1
2
3
4
5
6
7
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为根的树中，函数返回该节点．
明白了上面三点，可以直接看解法代码了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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，你说这是不是最近公共祖先呢？[7]

参考资料

1. 维基百科编者. 软件自由保护组织[G/OL]. 维基百科, 2019(20191114)[2019-11-14]. https://zh.wikipedia.org/w/index.php?title=%E8%BD%AF%E4%BB%B6%E8%87%AA%E7%94%B1%E4%BF%9D%E6%8A%A4%E7%BB%84%E7%BB%87&oldid=56869590. ↩
2. 起步- Git 简史.[G/OL].Git Book. https://git-scm.com/book/zh/v2/%E8%B5%B7%E6%AD%A5-Git-%E7%AE%80%E5%8F%B2 ↩
3. 维基百科编者. Git[G/OL]. 维基百科, 2020(20201106)[2020-11-06]. https://zh.wikipedia.org/w/index.php?title=Git&oldid=62682388. ↩
4. 自由与非自由软件的分类 https://www.gnu.org/philosophy/categories.zh-cn.html ↩
5. Linux、GNU和自由 https://www.gnu.org/philosophy/linux-gnu-freedom.zh-cn.html ↩
6. https://www.gnu.org/ ↩
7. labuladong. 用 Git 来讲讲二叉树最近公共祖先[G/OL]. 微信公众号—labuladong, 2020(20200609)[2020-06-09]. http://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485561&idx=1&sn=a394ba978283819da1eb34a256f6915b ↩
8. Git 内部原理 - Git 引用.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86-Git-%E5%BC%95%E7%94%A8 ↩
9. Git 分支 - 分支的新建与合并.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%88%86%E6%94%AF-%E5%88%86%E6%94%AF%E7%9A%84%E6%96%B0%E5%BB%BA%E4%B8%8E%E5%90%88%E5%B9%B6 ↩
10. Git 分支 - 远程分支.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%88%86%E6%94%AF-%E8%BF%9C%E7%A8%8B%E5%88%86%E6%94%AF ↩
11. https://learngitbranching.js.org/?locale=zh_CN ↩
12. https://github.com/pcottle/learnGitBranching ↩
13. 起步- Git 是什么？.[G/OL].Git Book.https://git-scm.com/book/zh/v2/%E8%B5%B7%E6%AD%A5-Git-%E6%98%AF%E4%BB%80%E4%B9%88%EF%BC%9F ↩
关注我

链接

分类

最新文章

归档

标签

AF_XDP2
ArchLinux1
AssemblyLanguage1
BPF2
BUUCTF1
C9
C++3
CTF1
Cache1
Calculus1
Crypto3
CyberspaceSecurity2
DNSDist2
Fastbin1
GNU/Linux10
Glibc1
Heap3
IPv61
Kernel1
Linux3
Network1
NumberTheory1
OperatingSystem2
PWN4
Powerdns2
Reverse1
STL1
Tcache2
Tools1
UAF1
UnsortBin1
WriteUp2
XDP2
calloc1
eBPF2
git1
io_uring1
kernel2
pdns2
xsk2
×