Git引出一個經(jīng)典的算法問題：最近公共祖先

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

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

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

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

那么問題來了，Git 是如何合并兩條分支并檢測沖突的呢？

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

這個過程中，Git 是這么做的：

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

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

尋找一個元素

先不管最近公共祖先問題，我請你實現(xiàn)一個簡單的算法：

給你輸入一棵沒有重復元素的二叉樹根節(jié)點root和一個目標值val，請你寫一個函數(shù)尋找樹中值為val的節(jié)點。

函數(shù)簽名如下：

TreeNodefind(TreeNoderoot,intval);

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

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

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

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

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

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

這段代碼也可以達到目的，但是實際運行的效率會低一些，原因也很簡單，如果你能夠在左子樹找到目標節(jié)點，還有沒有必要去右子樹找了？沒有必要。但這段代碼還是會去右子樹找一圈，所以效率相對差一些。

更進一步，我把對root.val的判斷從前序位置移動到后序位置：

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

這段代碼相當于你先去左右子樹找，然后才檢查root，依然可以到達目的，但是效率會進一步下降。因為這種寫法必然會遍歷二叉樹的每一個節(jié)點。

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

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

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

TreeNodefind(TreeNoderoot,intval1,intval2);

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

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

returnleft!=null?left:right;
}

為什么要寫這樣一個奇怪的find函數(shù)呢？因為最近公共祖先系列問題的解法都是把這個函數(shù)作為框架的。

下面一道一道題目來看。

秒殺五道題目

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

給你輸入一棵不含重復值的二叉樹，以及存在于樹中的兩個節(jié)點p和q，請你計算p和q的最近公共祖先節(jié)點。

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

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

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

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

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

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

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

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

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

returnleft!=null?left:right;
}

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

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

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

這樣，標準的最近公共祖先問題就解決了，接下來看看這個題目有什么變體。

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

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

函數(shù)簽名如下：

TreeNodelowestCommonAncestor(TreeNoderoot,TreeNode[]nodes);

比如還是這棵二叉樹：

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

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

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

returnfind(root,values);
}

//在二叉樹中尋找values的最近公共祖先節(jié)點
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)知道左右子樹是否存在目標值
if(left!=null&&right!=null){
//當前節(jié)點是LCA節(jié)點
returnroot;
}

returnleft!=null?left:right;
}

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

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

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

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

在解決標準的最近公共祖先問題時，我們在find函數(shù)的前序位置有這樣一段代碼：

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

我也進行了解釋，因為p和q都存在于樹中，所以這段代碼恰好可以解決最近公共祖先的第二種情況：

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

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

這種：

TreeNodefind(TreeNoderoot,intval){
if(root==null){
returnnull;
}
//先去左右子樹尋找
TreeNodeleft=find(root.left,val);
TreeNoderight=find(root.right,val);
//后序位置，判斷root是不是目標節(jié)點
if(root.val==val){
returnroot;
}
//root不是目標節(jié)點，再去看看哪邊的子樹找到了
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é)點
TreeNodefind(TreeNoderoot,intval1,intval2){
if(root==null){
returnnull;
}
TreeNodeleft=find(root.left,val1,val2);
TreeNoderight=find(root.right,val1,val2);

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

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

returnleft!=null?left:right;
}

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

接下來，我們再變一變，如果讓你在二叉搜索樹中尋找p和q的最近公共祖先，應(yīng)該如何做呢？

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

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

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

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

在標準的最近公共祖先問題中，我們要在后序位置通過左右子樹的搜索結(jié)果來判斷當前節(jié)點是不是LCA：

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

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

但對于 BST 來說，根本不需要老老實實去遍歷子樹，由于 BST 左小右大的性質(zhì)，將當前節(jié)點的值與val1和val2作對比即可判斷當前節(jié)點是不是LCA：

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

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

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é)點
TreeNodefind(TreeNoderoot,intval1,intval2){
if(root==null){
returnnull;
}
if(root.val>val2){
//當前節(jié)點太大，去左子樹找
returnfind(root.left,val1,val2);
}
if(root.val//當前節(jié)點太小，去右子樹找
returnfind(root.right,val1,val2);
}
//val1<=?root.val?<=?val2
//則當前節(jié)點就是最近公共祖先
returnroot;
}

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

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

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

NodelowestCommonAncestor(Nodep,Nodeq);

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

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

給你輸入兩個單鏈表的頭結(jié)點p和q，這兩個單鏈表必然會相交，請你返回相交點。

我在前文單鏈表的六大解題套路中詳細講解過求鏈表交點的問題，具體思路在本文就不展開了，直接給出本題的解法代碼：

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

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