如果說(shuō)筆試的時(shí)候經(jīng)常遇到各種動(dòng)歸回溯的騷操作，那么面試會(huì)傾向于一些比較經(jīng)典的問(wèn)題，難度不算大，而且也比較實(shí)用。

本文就用 Git 引出一個(gè)經(jīng)典的算法問(wèn)題：最近公共祖先（Lowest Common Ancestor，簡(jiǎn)稱 LCA）。

git pull這個(gè)命令我們經(jīng)常會(huì)用，它默認(rèn)是使用merge方式將遠(yuǎn)端別人的修改拉到本地；如果帶上參數(shù)git pull -r，就會(huì)使用rebase的方式將遠(yuǎn)端修改拉到本地。

這二者最直觀的區(qū)別就是：merge方式合并的分支會(huì)看到很多「分叉」，而rebase方式合并的分支就是一條直線。但無(wú)論哪種方式，如果存在沖突，Git 都會(huì)檢測(cè)出來(lái)并讓你手動(dòng)解決沖突。

那么問(wèn)題來(lái)了，Git 是如何合并兩條分支并檢測(cè)沖突的呢？

以rebase命令為例，比如下圖的情況，我站在dev分支執(zhí)行git rebase master，然后dev就會(huì)接到master分支之上：

這個(gè)過(guò)程中，Git 是這么做的：

首先，找到這兩條分支的最近公共祖先LCA，然后從master節(jié)點(diǎn)開始，重演LCA到dev的commit的修改，如果這些修改和LCA到master的commit有沖突，就會(huì)提示你手動(dòng)解決沖突，最后的結(jié)果就是把dev的分支完全接到master上面。

那么，Git 是如何找到兩條不同分支的最近公共祖先的呢？這就是一個(gè)經(jīng)典的算法問(wèn)題了，下面我來(lái)由淺入深講一講。

尋找一個(gè)元素

先不管最近公共祖先問(wèn)題，我請(qǐng)你實(shí)現(xiàn)一個(gè)簡(jiǎn)單的算法：

給你輸入一棵沒(méi)有重復(fù)元素的二叉樹根節(jié)點(diǎn)root和一個(gè)目標(biāo)值val，請(qǐng)你寫一個(gè)函數(shù)尋找樹中值為val的節(jié)點(diǎn)。

函數(shù)簽名如下：

TreeNodefind(TreeNoderoot,intval);

這個(gè)函數(shù)應(yīng)該很容易實(shí)現(xiàn)對(duì)吧，比如我這樣寫代碼：

//定義：在以 root 為根的二叉樹中尋找值為 val 的節(jié)點(diǎn)
TreeNodefind(TreeNoderoot,intval){
//basecase
if(root==null){
returnnull;
}
//看看root.val是不是要找的
if(root.val==val){
returnroot;
}
//root不是目標(biāo)節(jié)點(diǎn)，那就去左子樹找
TreeNodeleft=find(root.left,val);
if(left!=null){
returnleft;
}
//左子樹找不著，那就去右子樹找
TreeNoderight=find(root.right,val);
if(right!=null){
returnright;
}
//實(shí)在找不到了
returnnull;
}

這段代碼應(yīng)該不用我多解釋了，但我基于這段代碼做一些簡(jiǎn)單的改寫，請(qǐng)你分析一下我的改動(dòng)會(huì)造成什么影響。

PS：如果你沒(méi)讀過(guò)前文東哥帶你刷二叉樹（綱領(lǐng)篇），強(qiáng)烈建議閱讀一下，理解二叉樹前中后序遍歷的奧義。

首先，我修改一下 return 的位置：

TreeNodefind(TreeNoderoot,intval){
if(root==null){
returnnull;
}
//前序位置
if(root.val==val){
returnroot;
}
//root不是目標(biāo)節(jié)點(diǎn)，去左右子樹尋找
TreeNodeleft=find(root.left,val);
TreeNoderight=find(root.right,val);
//看看哪邊找到了
returnleft!=null?left:right;
}

這段代碼也可以達(dá)到目的，但是實(shí)際運(yùn)行的效率會(huì)低一些，原因也很簡(jiǎn)單，如果你能夠在左子樹找到目標(biāo)節(jié)點(diǎn)，還有沒(méi)有必要去右子樹找了？沒(méi)有必要。但這段代碼還是會(huì)去右子樹找一圈，所以效率相對(duì)差一些。

更進(jìn)一步，我把對(duì)root.val的判斷從前序位置移動(dòng)到后序位置：

TreeNodefind(TreeNoderoot,intval){
if(root==null){
returnnull;
}
//先去左右子樹尋找
TreeNodeleft=find(root.left,val);
TreeNoderight=find(root.right,val);
//后序位置，看看root是不是目標(biāo)節(jié)點(diǎn)
if(root.val==val){
returnroot;
}
//root不是目標(biāo)節(jié)點(diǎn)，再去看看哪邊的子樹找到了
returnleft!=null?left:right;
}

這段代碼相當(dāng)于你先去左右子樹找，然后才檢查root，依然可以到達(dá)目的，但是效率會(huì)進(jìn)一步下降。因?yàn)檫@種寫法必然會(huì)遍歷二叉樹的每一個(gè)節(jié)點(diǎn)。

對(duì)于之前的解法，你在前序位置就檢查root，如果輸入的二叉樹根節(jié)點(diǎn)的值恰好就是目標(biāo)值val，那么函數(shù)直接結(jié)束了，其他的節(jié)點(diǎn)根本不用搜索。

但如果你在后序位置判斷，那么就算根節(jié)點(diǎn)就是目標(biāo)節(jié)點(diǎn)，你也要去左右子樹遍歷完所有節(jié)點(diǎn)才能判斷出來(lái)。

最后，我再改一下題目，現(xiàn)在不讓你找值為val的節(jié)點(diǎn)，而是尋找值為val1或val2的節(jié)點(diǎn)，函數(shù)簽名如下：

TreeNodefind(TreeNoderoot,intval1,intval2);

這和我們第一次實(shí)現(xiàn)的find函數(shù)基本上是一樣的，而且你應(yīng)該知道可以有多種寫法，我選擇這樣寫代碼：

//定義：在以 root 為根的二叉樹中尋找值為 val1 或 val2 的節(jié)點(diǎn)
TreeNodefind(TreeNoderoot,intval1,intval2){
//basecase
if(root==null){
returnnull;
}
//前序位置，看看root是不是目標(biāo)值
if(root.val==val1||root.val==val2){
returnroot;
}
//去左右子樹尋找
TreeNodeleft=find(root.left,val1,val2);
TreeNoderight=find(root.right,val1,val2);
//后序位置，已經(jīng)知道左右子樹是否存在目標(biāo)值

returnleft!=null?left:right;
}

為什么要寫這樣一個(gè)奇怪的find函數(shù)呢？因?yàn)樽罱沧嫦认盗袉?wèn)題的解法都是把這個(gè)函數(shù)作為框架的。

下面一道一道題目來(lái)看。

秒殺五道題目

先來(lái)看看力扣第 236 題「二叉樹的最近公共祖先」：

給你輸入一棵不含重復(fù)值的二叉樹，以及存在于樹中的兩個(gè)節(jié)點(diǎn)p和q，請(qǐng)你計(jì)算p和q的最近公共祖先節(jié)點(diǎn)。

PS：后文我用LCA（Lowest Common Ancestor）作為最近公共祖先節(jié)點(diǎn)的縮寫。

比如輸入這樣一棵二叉樹：

如果p是節(jié)點(diǎn)6，q是節(jié)點(diǎn)7，那么它倆的LCA就是節(jié)點(diǎn)5：

當(dāng)然，p和q本身也可能是LCA，比如這種情況q本身就是LCA節(jié)點(diǎn)：

兩個(gè)節(jié)點(diǎn)的最近公共祖先其實(shí)就是這兩個(gè)節(jié)點(diǎn)向根節(jié)點(diǎn)的「延長(zhǎng)線」的交匯點(diǎn)，那么對(duì)于任意一個(gè)節(jié)點(diǎn)，它怎么才能知道自己是不是p和q的最近公共祖先？

如果一個(gè)節(jié)點(diǎn)能夠在它的左右子樹中分別找到p和q，則該節(jié)點(diǎn)為LCA節(jié)點(diǎn)。

這就要用到之前實(shí)現(xiàn)的find函數(shù)了，只需在后序位置添加一個(gè)判斷邏輯，即可改造成尋找最近公共祖先的解法代碼：

TreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){
returnfind(root,p.val,q.val);
}

//在二叉樹中尋找val1和val2的最近公共祖先節(jié)點(diǎn)
TreeNodefind(TreeNoderoot,intval1,intval2){
if(root==null){
returnnull;
}
//前序位置
if(root.val==val1||root.val==val2){
//如果遇到目標(biāo)值，直接返回
returnroot;
}
TreeNodeleft=find(root.left,val1,val2);
TreeNoderight=find(root.right,val1,val2);
//后序位置，已經(jīng)知道左右子樹是否存在目標(biāo)值
if(left!=null&&right!=null){
//當(dāng)前節(jié)點(diǎn)是LCA節(jié)點(diǎn)
returnroot;
}

returnleft!=null?left:right;
}

在find函數(shù)的后序位置，如果發(fā)現(xiàn)left和right都非空，就說(shuō)明當(dāng)前節(jié)點(diǎn)是LCA節(jié)點(diǎn)，即解決了第一種情況：

在find函數(shù)的前序位置，如果找到一個(gè)值為val1或val2的節(jié)點(diǎn)則直接返回，恰好解決了第二種情況：

因?yàn)轭}目說(shuō)了p和q一定存在于二叉樹中(這點(diǎn)很重要），所以即便我們遇到q就直接返回，根本沒(méi)遍歷到p，也依然可以斷定p在q底下，q就是LCA節(jié)點(diǎn)。

這樣，標(biāo)準(zhǔn)的最近公共祖先問(wèn)題就解決了，接下來(lái)看看這個(gè)題目有什么變體。

比如力扣第 1676 題「二叉樹的最近公共祖先 IV」：

依然給你輸入一棵不含重復(fù)值的二叉樹，但這次不是給你輸入p和q兩個(gè)節(jié)點(diǎn)了，而是給你輸入一個(gè)包含若干節(jié)點(diǎn)的列表nodes（這些節(jié)點(diǎn)都存在于二叉樹中），讓你算這些節(jié)點(diǎn)的最近公共祖先。

函數(shù)簽名如下：

TreeNodelowestCommonAncestor(TreeNoderoot,TreeNode[]nodes);

比如還是這棵二叉樹：

輸入nodes = [7,4,6]，那么函數(shù)應(yīng)該返回節(jié)點(diǎn)5。

看起來(lái)怪嚇人的，實(shí)則解法邏輯是一樣的，把剛才的代碼邏輯稍加改造即可解決這道題：

TreeNodelowestCommonAncestor(TreeNoderoot,TreeNode[]nodes){
//將列表轉(zhuǎn)化成哈希集合，便于判斷元素是否存在
HashSetvalues=newHashSet<>();
for(TreeNodenode:nodes){
values.add(node.val);
}

returnfind(root,values);
}

//在二叉樹中尋找values的最近公共祖先節(jié)點(diǎn)
TreeNodefind(TreeNoderoot,HashSetvalues){
if(root==null){
returnnull;
}
//前序位置
if(values.contains(root.val)){
returnroot;
}

TreeNodeleft=find(root.left,values);
TreeNoderight=find(root.right,values);
//后序位置，已經(jīng)知道左右子樹是否存在目標(biāo)值
if(left!=null&&right!=null){
//當(dāng)前節(jié)點(diǎn)是LCA節(jié)點(diǎn)
returnroot;
}

returnleft!=null?left:right;
}

有剛才的鋪墊，你類比一下應(yīng)該不難理解這個(gè)解法。

不過(guò)需要注意的是，這兩道題的題目都明確告訴我們這些節(jié)點(diǎn)必定存在于二叉樹中，如果沒(méi)有這個(gè)前提條件，就需要修改代碼了。

比如力扣第 1644 題「二叉樹的最近公共祖先 II」：

給你輸入一棵不含重復(fù)值的二叉樹的，以及兩個(gè)節(jié)點(diǎn)p和q，如果p或q不存在于樹中，則返回空指針，否則的話返回p和q的最近公共祖先節(jié)點(diǎn)。

在解決標(biāo)準(zhǔn)的最近公共祖先問(wèn)題時(shí)，我們?cè)?/span>find函數(shù)的前序位置有這樣一段代碼：

//前序位置
if(root.val==val1||root.val==val2){
//如果遇到目標(biāo)值，直接返回
returnroot;
}

我也進(jìn)行了解釋，因?yàn)?/span>p和q都存在于樹中，所以這段代碼恰好可以解決最近公共祖先的第二種情況：

但對(duì)于這道題來(lái)說(shuō)，p和q不一定存在于樹中，所以你不能遇到一個(gè)目標(biāo)值就直接返回，而應(yīng)該對(duì)二叉樹進(jìn)行完全搜索（遍歷每一個(gè)節(jié)點(diǎn)），如果發(fā)現(xiàn)p或q不存在于樹中，那么是不存在LCA的。

回想我在文章開頭分析的幾種find函數(shù)的寫法，哪種寫法能夠?qū)Χ鏄溥M(jìn)行完全搜索來(lái)著？

這種：

TreeNodefind(TreeNoderoot,intval){
if(root==null){
returnnull;
}
//先去左右子樹尋找
TreeNodeleft=find(root.left,val);
TreeNoderight=find(root.right,val);
//后序位置，判斷root是不是目標(biāo)節(jié)點(diǎn)
if(root.val==val){
returnroot;
}
//root不是目標(biāo)節(jié)點(diǎn)，再去看看哪邊的子樹找到了
returnleft!=null?left:right;
}

那么解決這道題也是類似的，我們只需要把前序位置的判斷邏輯放到后序位置即可：

//用于記錄p和q是否存在于二叉樹中
booleanfoundP=false,foundQ=false;

TreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){
TreeNoderes=find(root,p.val,q.val);
if(!foundP||!foundQ){
returnnull;
}
//p和q都存在二叉樹中，才有公共祖先
returnres;
}

//在二叉樹中尋找val1和val2的最近公共祖先節(jié)點(diǎn)
TreeNodefind(TreeNoderoot,intval1,intval2){
if(root==null){
returnnull;
}
TreeNodeleft=find(root.left,val1,val2);
TreeNoderight=find(root.right,val1,val2);

//后序位置，判斷當(dāng)前節(jié)點(diǎn)是不是LCA節(jié)點(diǎn)
if(left!=null&&right!=null){
returnroot;
}

//后序位置，判斷當(dāng)前節(jié)點(diǎn)是不是目標(biāo)值
if(root.val==val1||root.val==val2){
//找到了，記錄一下
if(root.val==val1)foundP=true;
if(root.val==val2)foundQ=true;
returnroot;
}

returnleft!=null?left:right;
}

這樣改造，對(duì)二叉樹進(jìn)行完全搜索，同時(shí)記錄p和q是否同時(shí)存在樹中，從而滿足題目的要求。

接下來(lái)，我們?cè)僮円蛔?，如果讓你在二叉搜索樹中尋?/span>p和q的最近公共祖先，應(yīng)該如何做呢？

PS：二叉搜索樹相關(guān)的題目詳解見東哥帶你刷二叉搜索樹。

看力扣第 235 題「二叉搜索樹的最近公共祖先」：

給你輸入一棵不含重復(fù)值的二叉搜索樹，以及存在于樹中的兩個(gè)節(jié)點(diǎn)p和q，請(qǐng)你計(jì)算p和q的最近公共祖先節(jié)點(diǎn)。

把之前的解法代碼復(fù)制過(guò)來(lái)肯定也可以解決這道題，但沒(méi)有用到 BST「左小右大」的性質(zhì)，顯然效率不是最高的。

在標(biāo)準(zhǔn)的最近公共祖先問(wèn)題中，我們要在后序位置通過(guò)左右子樹的搜索結(jié)果來(lái)判斷當(dāng)前節(jié)點(diǎn)是不是LCA：

TreeNodeleft=find(root.left,val1,val2);
TreeNoderight=find(root.right,val1,val2);

//后序位置，判斷當(dāng)前節(jié)點(diǎn)是不是LCA節(jié)點(diǎn)
if(left!=null&&right!=null){
returnroot;
}

但對(duì)于 BST 來(lái)說(shuō)，根本不需要老老實(shí)實(shí)去遍歷子樹，由于 BST 左小右大的性質(zhì)，將當(dāng)前節(jié)點(diǎn)的值與val1和val2作對(duì)比即可判斷當(dāng)前節(jié)點(diǎn)是不是LCA：

假設(shè)val1 < val2，那么val1 <= root.val <= val2則說(shuō)明當(dāng)前節(jié)點(diǎn)就是LCA；若root.val比val1還小，則需要去值更大的右子樹尋找LCA；若root.val比val2還大，則需要去值更小的左子樹尋找LCA。

依據(jù)這個(gè)思路就可以寫出解法代碼：

TreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){
//保證val1較小，val2較大
intval1=Math.min(p.val,q.val);
intval2=Math.max(p.val,q.val);
returnfind(root,val1,val2);
}

//在BST中尋找val1和val2的最近公共祖先節(jié)點(diǎn)
TreeNodefind(TreeNoderoot,intval1,intval2){
if(root==null){
returnnull;
}
if(root.val>val2){
//當(dāng)前節(jié)點(diǎn)太大，去左子樹找
returnfind(root.left,val1,val2);
}
if(root.val//當(dāng)前節(jié)點(diǎn)太小，去右子樹找
returnfind(root.right,val1,val2);
}
//val1<=?root.val?<=?val2
//則當(dāng)前節(jié)點(diǎn)就是最近公共祖先
returnroot;
}

再看最后一道最近公共祖先的題目吧，力扣第 1650 題「二叉樹的最近公共祖先 III」，這次輸入的二叉樹節(jié)點(diǎn)比較特殊，包含指向父節(jié)點(diǎn)的指針：

classNode{
intval;
Nodeleft;
Noderight;
Nodeparent;
};

給你輸入一棵存在于二叉樹中的兩個(gè)節(jié)點(diǎn)p和q，請(qǐng)你返回它們的最近公共祖先，函數(shù)簽名如下：

NodelowestCommonAncestor(Nodep,Nodeq);

由于節(jié)點(diǎn)中包含父節(jié)點(diǎn)的指針，所以二叉樹的根節(jié)點(diǎn)就沒(méi)必要輸入了。

這道題其實(shí)不是公共祖先的問(wèn)題，而是單鏈表相交的問(wèn)題，你把parent指針想象成單鏈表的next指針，題目就變成了：

給你輸入兩個(gè)單鏈表的頭結(jié)點(diǎn)p和q，這兩個(gè)單鏈表必然會(huì)相交，請(qǐng)你返回相交點(diǎn)。

我在前文單鏈表的六大解題套路中詳細(xì)講解過(guò)求鏈表交點(diǎn)的問(wèn)題，具體思路在本文就不展開了，直接給出本題的解法代碼：

NodelowestCommonAncestor(Nodep,Nodeq){
//施展鏈表雙指針技巧
Nodea=p,b=q;
while(a!=b){
//a走一步，如果走到根節(jié)點(diǎn)，轉(zhuǎn)到q節(jié)點(diǎn)
if(a==null)a=q;
elsea=a.parent;
//b走一步，如果走到根節(jié)點(diǎn)，轉(zhuǎn)到p節(jié)點(diǎn)
if(b==null)b=p;
elseb=b.parent;
}
returna;
}

至此，5 道最近公共祖先的題目就全部講完了，前 3 道題目從一個(gè)基本的find函數(shù)衍生出解法，后 2 道比較特殊，分別利用了 BST 和單鏈表相關(guān)的技巧，希望本文對(duì)你有啟發(fā)。