1. 從一次線上故障說起為什么LCA值得你花時間搞懂去年幫一個朋友排查他們內(nèi)部工具的一個性能問題場景很典型一個組織架構(gòu)樹大概三萬多節(jié)點每次要計算兩個員工在組織樹里的最近共同上級。他們最初的實現(xiàn)是暴力往上爬——把A的所有祖先塞進一個集合然后B從自己開始往上走遇到的第一個在集合里的節(jié)點就是答案。單次查詢看著不慢幾十毫秒但架不住前端一個頁面要批量算幾百對頁面直接卡到轉(zhuǎn)圈。這個問題的本質(zhì)就是LCALowest Common Ancestor最近公共祖先。聽起來像是算法競賽里的東西但只要你處理過任何樹形結(jié)構(gòu)——組織架構(gòu)、文件目錄、DOM節(jié)點、分類體系、依賴關(guān)系圖——你遲早會撞上它。而且一旦數(shù)據(jù)量上去暴力解法就會原形畢露。這篇內(nèi)容我打算把LCA這件事從頭到尾講透。不是那種背個倍增模板就完事的講法而是把為什么會有多種解法、每種解法到底在權(quán)衡什么、什么場景該選哪個、寫的時候哪里最容易翻車這些真正影響你落地的東西說清楚。適合已經(jīng)會寫基礎(chǔ)樹遍歷、但一遇到樹上路徑查詢就發(fā)怵的開發(fā)者也適合想系統(tǒng)梳理一遍這塊知識的老手?？赐昴銘?yīng)該能做到拿到一個問題先判斷它是不是LCA再根據(jù)數(shù)據(jù)規(guī)模和查詢次數(shù)直接選出合適的方案而不是無腦套模板。2. LCA到底在解決什么問題把共同祖先翻譯成人話2.1 用家族樹理解最近公共祖先先把這個概念用最樸素的方式說清楚。想象一棵家族樹根節(jié)點是最老的祖先往下每一層是下一代。現(xiàn)在給你兩個人問他倆血緣關(guān)系最近的那個共同長輩是誰注意最近兩個字是關(guān)鍵。往上數(shù)所有共同的長輩都算公共祖先但我們要的是**深度最大離他倆最近**的那一個。比如你和你堂哥你們的爺爺是LCA但曾祖父也是共同祖先只不過曾祖父更遠不是最近的。形式化一點給定一棵有根樹對于節(jié)點u和vLCA(u, v)是同時滿足是u的祖先且是v的祖先的節(jié)點中深度最大的那個。這里祖先通常包含節(jié)點自己——也就是說如果u本身就是v的祖先那LCA就是u。這個約定很重要很多實現(xiàn)細節(jié)都跟它有關(guān)。2.2 為什么暴力爬樹會崩復(fù)雜度賬要算清楚最直覺的做法有兩種。第一種是剛才說的集合法把u到根的路徑全標(biāo)記然后v往上走找第一個標(biāo)記點。第二種是先把兩個節(jié)點提到同一深度然后一起往上走直到相遇。這兩種做法單次查詢的復(fù)雜度都是O(樹高)。問題就出在這個樹高上。如果樹比較平衡高度是log級別那還行但現(xiàn)實中的樹經(jīng)常退化成一條鏈——比如一個層層審批的組織、一個深度嵌套的目錄、一條長依賴鏈。這時候樹高就是節(jié)點數(shù)n單次查詢O(n)查詢m次就是O(nm)。三萬個節(jié)點、幾百次查詢直接就是千萬級操作卡頓是必然的。所以LCA的核心矛盾就一句話能不能把單次查詢從O(樹高)壓到O(log n)甚至O(1)代價是預(yù)處理。后面講的所有算法本質(zhì)上都是在這條權(quán)衡線上找不同的位置。2.3 哪些真實場景會用到LCA別以為這只是刷題用的。我梳理幾個實際會碰到的組織架構(gòu)/權(quán)限系統(tǒng)判斷兩個員工的共同上級用于審批流、權(quán)限繼承、匯報關(guān)系展示。文件系統(tǒng)求兩個路徑的最近公共目錄做相對路徑計算、文件同步的差異定位。前端DOM操作找兩個節(jié)點的最近公共父節(jié)點用于事件委托、選區(qū)處理、虛擬DOM diff。版本控制/依賴分析在提交歷史或依賴樹里找共同基點判斷分支從哪分叉。生物信息學(xué)進化樹里找物種的共同祖先。網(wǎng)絡(luò)路由在某些樹形拓撲里找共同上游節(jié)點?？闯鰜砹税芍灰愕臄?shù)據(jù)是樹形或者能轉(zhuǎn)成樹形LCA就是個繞不開的基礎(chǔ)操作。理解了它等于拿到了一把處理樹形查詢的萬能鑰匙。3. 倍增法最通用的LCA解法也是面試最愛問的3.1 倍增的核心思想用二進制跳躍代替一步步爬倍增法Binary Lifting是我最推薦的入門方案因為它通用、好寫、好調(diào)而且能順帶解決一堆衍生問題比如求路徑上第k個祖先、路徑長度等。它的核心思想特別巧妙與其一步一步往上爬不如一次跳2的冪次步。就像你要走1000米不會一米一米挪而是先走512米、再256米……用二進制拆分快速到達。具體做法是預(yù)處理一個跳表up[i][j]表示節(jié)點i往上跳2^j步后到達的祖先。這個表可以遞推出來up[i][0] parent[i] // 跳1步就是父節(jié)點 up[i][j] up[ up[i][j-1] ][j-1] // 跳2^j步 先跳2^(j-1)再跳2^(j-1)第二行的遞推是整個算法的靈魂。它把跳一大步拆成跳兩小步從而能用已經(jīng)算好的小步結(jié)果推出大步結(jié)果。這就是典型的動態(tài)規(guī)劃思想也是倍增法名字的由來。3.2 預(yù)處理一遍DFS把跳表建起來預(yù)處理分兩步。第一步是DFS/BFS求出每個節(jié)點的深度depth[i]和直接父節(jié)點parent[i]。第二步就是按上面的遞推式填up表。關(guān)于j的上界取LOG ceil(log2(n)) 1就夠了。因為樹最高n層任何跳躍需求都能用不超過log2(n)位的二進制表示。多留一位是防止邊界越界。import sys sys.setrecursionlimit(300000) def preprocess(n, adj, root): LOG (n).bit_length() # 等價于 ceil(log2(n1)) depth [0] * (n 1) up [[0] * LOG for _ in range(n 1)] # 迭代式DFS避免遞歸爆棧 parent [0] * (n 1) order [] stack [root] visited [False] * (n 1) visited[root] True while stack: u stack.pop() order.append(u) for v in adj[u]: if not visited[v]: visited[v] True parent[v] u depth[v] depth[u] 1 stack.append(v) # 填跳表 for i in range(1, n 1): up[i][0] parent[i] for j in range(1, LOG): for i in range(1, n 1): up[i][j] up[ up[i][j-1] ][j-1] return depth, up, LOG這里有個實操細節(jié)值得說我強烈建議用迭代式DFS而不是遞歸。遞歸寫起來是簡潔但樹一深比如退化成鏈Python默認遞歸深度1000直接爆棧C雖然棧大一些但幾萬層也懸。迭代式雖然代碼長一點但穩(wěn)。這個坑我踩過不止一次線上環(huán)境可不會給你調(diào)遞歸深度的機會。3.3 查詢先對齊深度再一起往上跳查詢LCA(u, v)分兩個階段邏輯非常清晰階段一把深的那個提到和淺的一樣深。假設(shè)depth[u] depth[v]那就把u往上跳depth[u] - depth[v]步。這個差值用二進制拆解對應(yīng)到跳表上就是如果差值的第j位是1就跳2^j步。階段二如果此時u v說明v本來就是u的祖先直接返回。否則兩個節(jié)點一起往上跳從大到小嘗試。關(guān)鍵技巧是只要跳完之后兩個節(jié)點還不相等就跳。這樣最后一定會停在LCA的正下方再往上一步就是答案。def lca(u, v, depth, up, LOG): if depth[u] depth[v]: u, v v, u # 階段一對齊深度 diff depth[u] - depth[v] for j in range(LOG): if diff (1 j): u up[u][j] if u v: return u # 階段二一起往上跳 for j in range(LOG - 1, -1, -1): if up[u][j] ! up[v][j]: u up[u][j] v up[v][j] return up[u][0]階段二那個從大到小的循環(huán)方向特別重要必須從高位往低位試。因為我們要盡可能跳得遠但又不能跳過LCA。從大往小試能保證最后停在最近的位置。如果從小到大試會跳得不夠遠邏輯就錯了。這個細節(jié)很多人第一次寫會搞反。3.4 倍增法的復(fù)雜度與適用邊界預(yù)處理時間O(n log n)空間O(n log n)單次查詢O(log n)。這個復(fù)雜度對于絕大多數(shù)場景都夠用了。它的優(yōu)勢是通用性極強不要求樹是靜態(tài)的雖然動態(tài)更新跳表比較麻煩能處理任意形態(tài)的樹還能順便支持求第k個祖先這類操作。缺點是空間是n log n如果n到了百萬級內(nèi)存會有點吃緊。提示如果n特別大比如10^6以上而查詢次數(shù)不多其實暴力法反而更劃算。別迷信高級算法選型要看具體數(shù)據(jù)規(guī)模。4. Tarjan離線算法查詢多、樹不動時的效率之王4.1 離線思維把所有查詢攢起來一起算倍增法是在線的——來一個查詢答一個。但如果你的場景是一次性拿到所有查詢?nèi)缓笈砍鼋Y(jié)果那Tarjan離線算法往往更快。Tarjan的核心是DFS 并查集。它利用DFS的回溯特性在遍歷樹的過程中順便把所有查詢都解決了。單次查詢的均攤復(fù)雜度接近O(1)整體是O(n m·α(n))其中α是并查集的反阿克曼函數(shù)實際可以當(dāng)成常數(shù)。這個思路的巧妙之處在于它把查詢這件事融進了遍歷里而不是遍歷完再單獨查。對于查詢量巨大的場景比如m和n同量級甚至更大這個優(yōu)勢非常明顯。4.2 并查集在這里扮演什么角色理解Tarjan的關(guān)鍵是搞懂并查集維護的是什么。在DFS過程中每個節(jié)點有三種狀態(tài)未訪問、正在訪問在遞歸棧里、已訪問完子樹處理完畢。并查集維護的是已訪問完的節(jié)點的集合并且每個集合的代表元指向它當(dāng)前能追溯到的、還在遞歸棧里的那個祖先。當(dāng)DFS訪問到節(jié)點u處理所有跟u相關(guān)的查詢(u, v)時如果v還沒訪問跳過等以后v被訪問時再處理這對查詢。如果v已經(jīng)訪問完了那么v所在并查集集合的代表元就是LCA(u, v)。為什么因為v已經(jīng)處理完說明v的整棵子樹都遍歷過了而u還在棧里說明u是v的某個祖先方向上的節(jié)點。此時v能追溯到的、還在棧里的最深祖先恰好就是它和u的分叉點也就是LCA。4.3 完整實現(xiàn)與關(guān)鍵細節(jié)def tarjan_lca(n, adj, root, queries): # queries[u] [(v, query_id), ...] parent list(range(n 1)) # 并查集 ancestor [0] * (n 1) # 集合代表元對應(yīng)的祖先 visited [False] * (n 1) answer [0] * len(queries) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路徑壓縮 x parent[x] return x def dfs(u): visited[u] True ancestor[find(u)] u for v in adj[u]: if not visited[v]: dfs(v) parent[find(v)] find(u) # 合并子樹到u ancestor[find(u)] u # 處理與u相關(guān)的查詢 for (v, qid) in queries[u]: if visited[v]: answer[qid] ancestor[find(v)] dfs(root) return answer幾個容易翻車的點第一ancestor的更新時機。每次合并完子樹后要把合并后集合的ancestor重新指向u。因為合并后代表元可能變了不更新就會拿到錯誤的祖先。第二查詢要存雙向。因為處理(u,v)時可能v還沒訪問得等v被訪問時從v那邊再處理一次。所以queries[u]和queries[v]都要存這條查詢。第三遞歸深度問題。跟倍增法一樣深樹會爆棧。生產(chǎn)環(huán)境建議改迭代或者手動加大?？臻g。4.4 什么時候該選Tarjan而不是倍增判斷標(biāo)準(zhǔn)很簡單維度倍增法Tarjan離線查詢模式在線來一個答一個離線必須預(yù)先知道所有查詢單次查詢O(log n)均攤O(α(n))≈O(1)預(yù)處理O(n log n)無獨立預(yù)處理空間O(n log n)O(n m)實現(xiàn)難度中等中等偏上并查集易錯適用場景查詢少、需在線查詢海量、可離線如果你的查詢次數(shù)m遠大于nTarjan的均攤優(yōu)勢會非常明顯。但如果查詢是流式的、必須即時回答那只能選倍增。選型的第一原則永遠是先搞清楚你的查詢模式。5. 歐拉序 RMQ把LCA變成區(qū)間最值問題5.1 一個漂亮的轉(zhuǎn)化LCA等價于區(qū)間最小值這是我覺得LCA里最優(yōu)雅的一個思路。它把樹上問題轉(zhuǎn)化成了數(shù)組上的區(qū)間查詢問題。做法是對樹做一次DFS記錄歐拉序也叫DFS序的擴展版——每次進入一個節(jié)點記一次每次從子樹返回父節(jié)點時也記一次。這樣得到的序列長度是2n-1。同時記錄每個節(jié)點在序列中第一次出現(xiàn)的位置first[u]。關(guān)鍵結(jié)論LCA(u, v)就是歐拉序中first[u]到first[v]這段區(qū)間里深度最小的那個節(jié)點。為什么因為從u走到v在歐拉序上必然經(jīng)過它們的LCA而且LCA是這段路徑上深度最小的點。這個性質(zhì)把LCA問題完美地轉(zhuǎn)化成了**RMQ區(qū)間最小值查詢**問題。5.2 稀疏表ST表實現(xiàn)O(1)查詢既然變成了RMQ那就可以用經(jīng)典的ST表Sparse Table來做到O(1)查詢。ST表的預(yù)處理是O(n log n)查詢O(1)。import math def build_euler(n, adj, root): euler [] # 歐拉序存節(jié)點 depth_arr [] # 對應(yīng)深度 first [0] * (n 1) visited [False] * (n 1) def dfs(u, d): visited[u] True first[u] len(euler) euler.append(u) depth_arr.append(d) for v in adj[u]: if not visited[v]: dfs(v, d 1) euler.append(u) depth_arr.append(d) dfs(root, 0) return euler, depth_arr, first def build_st(depth_arr): m len(depth_arr) LOG m.bit_length() # st[i][j] 存區(qū)間 [i, i2^j-1] 中深度最小的節(jié)點在depth_arr中的下標(biāo) st [[0] * LOG for _ in range(m)] for i in range(m): st[i][0] i for j in range(1, LOG): for i in range(m - (1 j) 1): left st[i][j-1] right st[i (1 (j-1))][j-1] st[i][j] left if depth_arr[left] depth_arr[right] else right return st def query_lca(u, v, first, depth_arr, st, euler): l, r first[u], first[v] if l r: l, r r, l length r - l 1 k length.bit_length() - 1 left st[l][k] right st[r - (1 k) 1][k] idx left if depth_arr[left] depth_arr[right] else right return euler[idx]5.3 歐拉序方案的取舍這個方案的優(yōu)勢是查詢O(1)比倍增的O(log n)還快。而且思路清晰一旦理解了歐拉序的性質(zhì)代碼其實不難寫。但它有幾個明顯的代價空間更大歐拉序長度是2n-1ST表又是(2n) log(2n)比倍增的n log n大一倍左右。預(yù)處理常數(shù)大建ST表的雙重循環(huán)實際跑起來比倍增的預(yù)處理慢。只適合靜態(tài)樹樹一變整個歐拉序和ST表都要重建。所以我的經(jīng)驗是如果查詢量極大且樹完全靜態(tài)歐拉序ST表是最優(yōu)解否則倍增法更省心。別為了那點查詢速度提升把代碼復(fù)雜度拉高一大截維護成本也是成本。注意歐拉序的DFS同樣有遞歸深度問題。而且歐拉序長度是2n如果n很大光是存這個序列就要不少內(nèi)存選型前先估一下。6. 四種解法橫向?qū)Ρ纫粡埍韼湍阕鲞x型決策前面講了四種主流方案這里做個系統(tǒng)對比方便你直接查表決策。方案預(yù)處理單次查詢空間在線/離線最適合的場景暴力爬樹O(1)O(樹高)O(n)在線樹淺、查詢極少倍增法O(n log n)O(log n)O(n log n)在線通用首選查詢中等Tarjan離線無均攤O(α(n))O(nm)離線查詢海量、可離線歐拉序STO(n log n)O(1)O(n log n)在線查詢極多、樹靜態(tài)選型的決策鏈路我一般是這么走的第一步看查詢模式。流式在線查詢排除Tarjan能批量離線Tarjan值得考慮。第二步看數(shù)據(jù)規(guī)模。n小幾千以內(nèi)且查詢少暴力法最省事別過度設(shè)計。n大且查詢多上倍增或歐拉序。第三步看樹是否靜態(tài)。樹會動態(tài)變化倍增法改起來相對可控雖然也麻煩歐拉序基本要重建。第四步看查詢次數(shù)。查詢次數(shù)遠超n歐拉序的O(1)優(yōu)勢才體現(xiàn)得出來否則倍增的O(log n)完全夠用。我見過太多人一上來就寫歐拉序ST表結(jié)果數(shù)據(jù)規(guī)模才幾千純屬殺雞用牛刀代碼還容易寫錯。選型要匹配問題規(guī)模這是工程思維和刷題思維最大的區(qū)別。7. 實戰(zhàn)中那些文檔不會告訴你的坑7.1 根節(jié)點的父節(jié)點處理這是最經(jīng)典的坑。根節(jié)點沒有父節(jié)點那up[root][0]填什么填0假設(shè)節(jié)點編號從1開始還是填自己填0的話如果查詢時不小心跳到了0后續(xù)up[0][j]全是0可能掩蓋邏輯錯誤。填自己的話跳過頭會原地打轉(zhuǎn)。我的建議是填0并且在查詢邏輯里保證永遠不會真正用到0這個越界值——因為對齊深度和一起跳的過程理論上不會讓節(jié)點跳到根之上。但為了保險可以在填表時把up[0][j]都設(shè)成0讓越界訪問有個確定的兜底。7.2 深度對齊時的循環(huán)方向階段一對齊深度時for j in range(LOG)從小到大還是從大到小其實都可以因為我們是按二進制位判斷的每一位獨立。但階段二一起跳的時候必須從大到小。這兩個循環(huán)方向不一樣很多人寫著寫著就混了。記住口訣對齊深度看位一起跳看大小。7.3 多組測試數(shù)據(jù)的初始化如果是在競賽或批量處理場景多組測試數(shù)據(jù)之間一定要徹底重置所有數(shù)組。我見過因為up表沒清干凈上一組數(shù)據(jù)殘留導(dǎo)致答案錯誤的案例。Python里重新分配數(shù)組最省心C里記得memset或者重新構(gòu)造。7.4 節(jié)點編號從0還是從1開始這個看似小事實則影響巨大。從1開始的話0可以當(dāng)哨兵從0開始的話就沒有天然的哨兵值了。我個人的習(xí)慣是統(tǒng)一從1開始編號把0留作哨兵能省掉很多邊界判斷。如果輸入是從0開始的讀入時統(tǒng)一加1。7.5 遞歸改迭代的通用套路前面反復(fù)提到遞歸爆棧。改迭代的通用做法是手動維護一個棧棧里存(節(jié)點, 父節(jié)點, 狀態(tài))狀態(tài)標(biāo)記是第一次訪問還是回溯?；蛘吒唵蜗扔肂FS求出遍歷順序和父節(jié)點再按逆序處理回溯邏輯。對于倍增法其實只需要父節(jié)點和深度BFS一遍就夠了根本不需要DFS。這個優(yōu)化能同時解決爆棧和效率問題。8. 從LCA延伸出去幾個高頻衍生問題搞懂了LCA很多樹上查詢問題都能順手解決。這里列幾個最常見的延伸算是給你指個方向。樹上兩點距離。有了LCA距離公式就是depth[u] depth[v] - 2 * depth[lca(u,v)]。這個公式極其常用路徑長度、樹上最遠點對之類的問題都靠它。樹上路徑第k個節(jié)點。從u到v的路徑上第k個點先判斷k是否超過u到LCA的距離分兩種情況用倍增跳。這是倍增法跳表能力的直接應(yīng)用。判斷一個點是否在兩點路徑上。點w在u-v路徑上當(dāng)且僅當(dāng)lca(u,w)w且lca(w,v)ww是u的祖先且是v的祖先方向或者更準(zhǔn)確地用距離公式驗證。這類判斷在路徑覆蓋、樹上差分里很常見。樹上差分。給u到v的路徑上所有點加一個值可以用差分diff[u] 1, diff[v] 1, diff[lca] - 1, diff[parent(lca)] - 1最后子樹求和。這個技巧配合LCA能解決一大批路徑統(tǒng)計問題。這些延伸的共同點是LCA是它們的地基。地基打牢了上面的樓怎么蓋都行。所以別急著刷各種花哨的樹上問題先把LCA這幾種解法吃透后面會輕松很多。我個人在實際項目里的體會是真正高頻用到的其實就是倍增法這一種因為它通用、在線、好維護。Tarjan和歐拉序更像是特定場景的優(yōu)化手段知道原理、需要時能撿起來就行不必強求每種都背得滾瓜爛熟。把一種方案寫到閉著眼睛都不出錯比每種都半懂不懂要值錢得多。