讀完本文丐谋，你可以去力扣拿下如下題目：
-----------
如果說筆試的時候喜歡考各種動歸回溯的騷操作击纬，面試其實最喜歡考比較經(jīng)典的問題，難度不算太大琼腔，而且也比較實用寞秃。
上篇文章 四個命令玩轉(zhuǎn) Git 寫了 Git 最常用的命令斟叼，沒有提分支合并，其實分支合并沒什么困難的春寿，主要就是 merge 和 rebase 兩種方式朗涩。本文就用 Git 的 rebase 工作方式引出一個經(jīng)典的算法問題：最近公共祖先（Lowest Common Ancestor，簡稱 LCA）绑改。
比如 git pull 這個命令谢床，我們經(jīng)常會用，它默認(rèn)是使用 merge 方式將遠(yuǎn)端別人的修改拉到本地厘线；如果帶上參數(shù) git pull -r识腿，就會使用 rebase 的方式將遠(yuǎn)端修改拉到本地。
這二者最直觀的區(qū)別就是：merge 方式合并的分支會有很多「分叉」造壮，而 rebase 方式合并的分支就是一條直線渡讼。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目耳璧，全部發(fā)布在 labuladong的算法小抄硝全，持續(xù)更新。建議收藏楞抡，按照我的文章順序刷題伟众，掌握各種算法套路后投再入題海就如魚得水了。
對于多人協(xié)作召廷，merge 方式并不好凳厢，舉例來說，之前有很多朋友參加了在 GitHub 上的倉庫翻譯工作竞慢，GitHub 的 Pull Request 功能是使用 merge 方式先紫，所以你看 fucking-algorithm 倉庫的 Git 歷史：
畫面看起來很炫酷，但實際上我們并不希望出現(xiàn)這種情形的筹煮。你想想遮精，光是合并別人的代碼就這般群魔亂舞，如果說你本地還有多個開發(fā)分支，那畫面肯定更雜亂本冲，雜亂就意味著很容易出問題准脂，所以一般來說，實際工作中更推薦使用 rebase 方式合并代碼檬洞。
那么問題來了狸膏，rebase 是如何將兩條不同的分支合并到同一條分支的呢：
上圖的情況是，我站在 dev 分支添怔，使用 git rebase master湾戳，然后就會把 dev 接到 master 分支之上。Git 是這么做的：
首先广料，找到這兩條分支的最近公共祖先 LCA砾脑，然后從 master 節(jié)點開始，重演 LCA 到 dev 幾個 commit 的修改艾杏，如果這些修改和 LCA 到 master 的 commit 有沖突拦止，就會提示你手動解決沖突，最后的結(jié)果就是把 dev 的分支完全接到 master 上面糜颠。
那么汹族，Git 是如何找到兩條不同分支的最近公共祖先的呢？這就是一個經(jīng)典的算法問題了其兴，下面來詳解顶瞒。
二叉樹的最近公共祖先
這個問題可以在 LeetCode 上找到，看下題目：
函數(shù)的簽名如下：
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q);
root 節(jié)點確定了一棵二叉樹元旬，p 和 q 是這棵二叉樹上的兩個節(jié)點榴徐，讓你返回 p 節(jié)點和 q 節(jié)點的最近公共祖先節(jié)點。
我們前文 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維 就說過了匀归，所有二叉樹的套路都是一樣的：
void traverse(TreeNode root) {
// 前序遍歷
traverse(root.left)
// 中序遍歷
traverse(root.right)
// 后序遍歷
}
所以坑资，只要看到二叉樹的問題，先把這個框架寫出來準(zhǔn)沒問題：
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
}
現(xiàn)在我們思考如何添加一些細(xì)節(jié)穆端，把框架改造成解法袱贮。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目体啰，全部發(fā)布在 labuladong的算法小抄攒巍，持續(xù)更新。建議收藏荒勇，按照我的文章順序刷題柒莉，掌握各種算法套路后投再入題海就如魚得水了。
labuladong 告訴你沽翔，遇到任何遞歸型的問題兢孝，無非就是靈魂三問：
1、這個函數(shù)是干嘛的？
2跨蟹、這個函數(shù)參數(shù)中的變量是什么雳殊？
3、得到函數(shù)的遞歸結(jié)果喷市，你應(yīng)該干什么？
呵呵威恼，看到這靈魂三問品姓，你有沒有感覺到熟悉？本號的動態(tài)規(guī)劃系列文章箫措，篇篇都在說的動態(tài)規(guī)劃套路腹备，首先要明確的是什么？是不是要明確「定義」「狀態(tài)」「選擇」斤蔓，這仨不就是上面的靈魂三問嗎植酥？
下面我們就來看看如何回答這靈魂三問。
解法思路
首先看第一個問題弦牡，這個函數(shù)是干嘛的友驮？或者說，你給我描述一下 lowestCommonAncestor 這個函數(shù)的「定義」吧驾锰。
描述：給該函數(shù)輸入三個參數(shù) root卸留，p，q椭豫，它會返回一個節(jié)點耻瑟。
情況 1，如果 p 和 q 都在以 root 為根的樹中赏酥，函數(shù)返回的就是 p 和 q 的最近公共祖先節(jié)點喳整。
情況 2，那如果 p 和 q 都不在以 root 為根的樹中怎么辦呢裸扶？函數(shù)理所當(dāng)然地返回 null 唄框都。
情況 3，那如果 p 和 q 只有一個存在于 root 為根的樹中呢呵晨？函數(shù)就會返回那個節(jié)點瞬项。
題目說了輸入的 p 和 q 一定存在于以 root 為根的樹中，但是遞歸過程中何荚，以上三種情況都有可能發(fā)生囱淋，所以說這里要定義清楚，后續(xù)這些定義都會在代碼中體現(xiàn)餐塘。
OK妥衣，第一個問題就解決了，把這個定義記在腦子里，無論發(fā)生什么税手，都不要懷疑這個定義的正確性蜂筹，這是我們寫遞歸函數(shù)的基本素養(yǎng)。
然后來看第二個問題芦倒，這個函數(shù)的參數(shù)中艺挪，變量是什么？或者說兵扬，你描述一個這個函數(shù)的「狀態(tài)」吧麻裳。
描述：函數(shù)參數(shù)中的變量是 root，因為根據(jù)框架器钟，lowestCommonAncestor(root) 會遞歸調(diào)用 root.left 和 root.right津坑；至于 p 和 q，我們要求它倆的公共祖先傲霸，它倆肯定不會變化的疆瑰。
第二個問題也解決了，你也可以理解這是「狀態(tài)轉(zhuǎn)移」昙啄，每次遞歸在做什么穆役？不就是在把「以 root 為根」轉(zhuǎn)移成「以 root 的子節(jié)點為根」，不斷縮小問題規(guī)模嘛梳凛？
最后來看第三個問題孵睬，得到函數(shù)的遞歸結(jié)果，你該干嘛伶跷？或者說掰读，得到遞歸調(diào)用的結(jié)果后，你做什么「選擇」叭莫？
這就像動態(tài)規(guī)劃系列問題蹈集，怎么做選擇，需要觀察問題的性質(zhì)雇初，找規(guī)律拢肆。那么我們就得分析這個「最近公共祖先節(jié)點」有什么特點呢？剛才說了函數(shù)中的變量是 root 參數(shù)靖诗，所以這里都要圍繞 root 節(jié)點的情況來展開討論郭怪。
先想 base case，如果 root 為空刊橘，肯定得返回 null鄙才。如果 root 本身就是 p 或者 q，比如說 root 就是 p 節(jié)點吧促绵，如果 q 存在于以 root 為根的樹中攒庵，顯然 root 就是最近公共祖先嘴纺；即使 q 不存在于以 root 為根的樹中，按照情況 3 的定義浓冒，也應(yīng)該返回 root 節(jié)點栽渴。
以上兩種情況的 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);
}
現(xiàn)在就要面臨真正的挑戰(zhàn)了，用遞歸調(diào)用的結(jié)果 left 和 right 來搞點事情稳懒。根據(jù)剛才第一個問題中對函數(shù)的定義闲擦，我們繼續(xù)分情況討論：
情況 1，如果 p 和 q 都在以 root 為根的樹中场梆，那么 left 和 right 一定分別是 p 和 q（從 base case 看出來的）墅冷。
情況 2，如果 p 和 q 都不在以 root 為根的樹中辙谜，直接返回 null俺榆。
情況 3感昼，如果 p 和 q 只有一個存在于 root 為根的樹中装哆，函數(shù)返回該節(jié)點。
明白了上面三點定嗓，可以直接看解法代碼了：
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 出發(fā)往上走，第一次相交的節(jié)點就是這個 root矛市，你說這是不是最近公共祖先呢芙沥？
綜上，二叉樹的最近公共祖先就計算出來了浊吏。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章而昨，手把手帶刷 200 道力扣題目，建議收藏找田！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star歌憨，歡迎標(biāo)星！
