如果說筆試的時(shí)候經(jīng)常遇到各種動(dòng)歸回溯的騷操作，那么面試會(huì)傾向于一些比較經(jīng)典的問題，難度不算大，而且也比較實(shí)用。
本文就用 Git 引出一個(gè)經(jīng)典的算法問題：最近公共祖先（Lowest Common Ancestor，簡稱 LCA）。
git pull這個(gè)命令我們經(jīng)常會(huì)用，它默認(rèn)是使用merge方式將遠(yuǎn)端別人的修改拉到本地；如果帶上參數(shù)git pull -r，就會(huì)使用rebase的方式將遠(yuǎn)端修改拉到本地。
這二者最直觀的區(qū)別就是：merge方式合并的分支會(huì)看到很多「分叉」，而rebase方式合并的分支就是一條直線。但無論哪種方式，如果存在沖突，Git 都會(huì)檢測出來并讓你手動(dòng)解決沖突。
那么問題來了，Git 是如何合并兩條分支并檢測沖突的呢？
以rebase命令為例，比如下圖的情況，我站在dev分支執(zhí)行git rebase master，然后dev就會(huì)接到master分支之上：
這個(gè)過程中，Git 是這么做的：
首先，找到這兩條分支的最近公共祖先LCA，然后從master節(jié)點(diǎn)開始，重演LCA到dev的commit的修改，如果這些修改和LCA到master的commit有沖突，就會(huì)提示你手動(dòng)解決沖突，最后的結(jié)果就是把dev的分支完全接到master上面。
那么，Git 是如何找到兩條不同分支的最近公共祖先的呢？這就是一個(gè)經(jīng)典的算法問題了，下面我來由淺入深講一講。
尋找一個(gè)元素
先不管最近公共祖先問題，我請(qǐng)你實(shí)現(xiàn)一個(gè)簡單的算法：
給你輸入一棵沒有重復(fù)元素的二叉樹根節(jié)點(diǎn)root和一個(gè)目標(biāo)值val，請(qǐng)你寫一個(gè)函數(shù)尋找樹中值為val的節(jié)點(diǎn)。
函數(shù)簽名如下：
復(fù)制TreeNodefind(TreeNoderoot,intval);
這個(gè)函數(shù)應(yīng)該很容易實(shí)現(xiàn)對(duì)吧，比如我這樣寫代碼：
復(fù)制//定義：在以 root 為根的二叉樹中尋找值為 val 的節(jié)點(diǎn)TreeNodefind(TreeNoderoot,intval){//basecaseif(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)該不用我多解釋了，但我基于這段代碼做一些簡單的改寫，請(qǐng)你分析一下我的改動(dòng)會(huì)造成什么影響。
PS：如果你沒讀過前文東哥帶你刷二叉樹（綱領(lǐng)篇），強(qiáng)烈建議閱讀一下，理解二叉樹前中后序遍歷的奧義。
首先，我修改一下 return 的位置：
復(fù)制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ì)低一些，原因也很簡單，如果你能夠在左子樹找到目標(biāo)節(jié)點(diǎn)，還有沒有必要去右子樹找了？沒有必要。但這段代碼還是會(huì)去右子樹找一圈，所以效率相對(duì)差一些。
更進(jìn)一步，我把對(duì)root.val的判斷從前序位置移動(dòng)到后序位置：
復(fù)制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)才能判斷出來。
最后，我再改一下題目，現(xiàn)在不讓你找值為val的節(jié)點(diǎn)，而是尋找值為val1或val2的節(jié)點(diǎn)，函數(shù)簽名如下：
復(fù)制TreeNodefind(TreeNoderoot,intval1,intval2);
這和我們第一次實(shí)現(xiàn)的find函數(shù)基本上是一樣的，而且你應(yīng)該知道可以有多種寫法，我選擇這樣寫代碼：
復(fù)制//定義：在以 root 為根的二叉樹中尋找值為 val1 或 val2 的節(jié)點(diǎn)TreeNodefind(TreeNoderoot,intval1,intval2){//basecaseif(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)樽罱沧嫦认盗袉栴}的解法都是把這個(gè)函數(shù)作為框架的。
下面一道一道題目來看。
秒殺五道題目
先來看看力扣第 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)的「延長線」的交匯點(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è)判斷邏輯，即可改造成尋找最近公共祖先的解法代碼：
復(fù)制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都非空，就說明當(dāng)前節(jié)點(diǎn)是LCA節(jié)點(diǎn)，即解決了第一種情況：
在find函數(shù)的前序位置，如果找到一個(gè)值為val1或val2的節(jié)點(diǎn)則直接返回，恰好解決了第二種情況：
因?yàn)轭}目說了p和q一定存在于二叉樹中(這點(diǎn)很重要），所以即便我們遇到q就直接返回，根本沒遍歷到p，也依然可以斷定p在q底下，q就是LCA節(jié)點(diǎn)。
這樣，標(biāo)準(zhǔn)的最近公共祖先問題就解決了，接下來看看這個(gè)題目有什么變體。
比如力扣第 1676 題「二叉樹的最近公共祖先 IV」：
依然給你輸入一棵不含重復(fù)值的二叉樹，但這次不是給你輸入p和q兩個(gè)節(jié)點(diǎn)了，而是給你輸入一個(gè)包含若干節(jié)點(diǎn)的列表nodes（這些節(jié)點(diǎn)都存在于二叉樹中），讓你算這些節(jié)點(diǎn)的最近公共祖先。
函數(shù)簽名如下：
復(fù)制TreeNodelowestCommonAncestor(TreeNoderoot,TreeNode[]nodes);
比如還是這棵二叉樹：
輸入nodes = [7,4,6]，那么函數(shù)應(yīng)該返回節(jié)點(diǎn)5。
看起來怪嚇人的，實(shí)則解法邏輯是一樣的，把剛才的代碼邏輯稍加改造即可解決這道題：
復(fù)制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è)解法。
不過需要注意的是，這兩道題的題目都明確告訴我們這些節(jié)點(diǎn)必定存在于二叉樹中，如果沒有這個(gè)前提條件，就需要修改代碼了。
比如力扣第 1644 題「二叉樹的最近公共祖先 II」：
給你輸入一棵不含重復(fù)值的二叉樹的，以及兩個(gè)節(jié)點(diǎn)p和q，如果p或q不存在于樹中，則返回空指針，否則的話返回p和q的最近公共祖先節(jié)點(diǎn)。
在解決標(biāo)準(zhǔn)的最近公共祖先問題時(shí)，我們?cè)?/span>find函數(shù)的前序位置有這樣一段代碼：
復(fù)制//前序位置if(root.val==val1||root.val==val2){//如果遇到目標(biāo)值，直接返回returnroot;
}我也進(jìn)行了解釋，因?yàn)?/span>p和q都存在于樹中，所以這段代碼恰好可以解決最近公共祖先的第二種情況：
但對(duì)于這道題來說，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)行完全搜索來著？
這種：
復(fù)制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;
}那么解決這道題也是類似的，我們只需要把前序位置的判斷邏輯放到后序位置即可：
復(fù)制//用于記錄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í)存在樹中，從而滿足題目的要求。
接下來，我們?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ù)制過來肯定也可以解決這道題，但沒有用到 BST「左小右大」的性質(zhì)，顯然效率不是最高的。
在標(biāo)準(zhǔn)的最近公共祖先問題中，我們要在后序位置通過左右子樹的搜索結(jié)果來判斷當(dāng)前節(jié)點(diǎn)是不是LCA：
復(fù)制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 來說，根本不需要老老實(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則說明當(dāng)前節(jié)點(diǎn)就是LCA；若root.val比val1還小，則需要去值更大的右子樹尋找LCA；若root.val比val2還大，則需要去值更小的左子樹尋找LCA。
依據(jù)這個(gè)思路就可以寫出解法代碼：
復(fù)制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< val1) {
//當(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)的指針：
復(fù)制classNode{intval;
Nodeleft;
Noderight;
Nodeparent;
};給你輸入一棵存在于二叉樹中的兩個(gè)節(jié)點(diǎn)p和q，請(qǐng)你返回它們的最近公共祖先，函數(shù)簽名如下：
復(fù)制NodelowestCommonAncestor(Nodep,Nodeq);
由于節(jié)點(diǎn)中包含父節(jié)點(diǎn)的指針，所以二叉樹的根節(jié)點(diǎn)就沒必要輸入了。
這道題其實(shí)不是公共祖先的問題，而是單鏈表相交的問題，你把parent指針想象成單鏈表的next指針，題目就變成了：
給你輸入兩個(gè)單鏈表的頭結(jié)點(diǎn)p和q，這兩個(gè)單鏈表必然會(huì)相交，請(qǐng)你返回相交點(diǎn)。
我在前文單鏈表的六大解題套路中詳細(xì)講解過求鏈表交點(diǎn)的問題，具體思路在本文就不展開了，直接給出本題的解法代碼：
復(fù)制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ā)。
審核編輯 ：李倩
