常用英文

最近公共祖先（Lowest Common Ancestor，簡稱LCA）
posterity，英語單詞，主要用作名詞，作名詞時譯為“子孫，后裔；后代”。

什么是深度優先搜索

深度優先搜索，Depth First Search, 簡稱DFS。它從初始節點出發，按預定的順序擴展到下一個節點，然后從下一節點出發繼續擴展新的節點，不斷遞歸執行這個過程，直到某個節點不能再擴展下一個節點為止。此時，則返回上一個節點重新尋找一個新的擴展節點。如此搜索下去，直到找到目標節點，或者搜索完所有節點為止。
通俗的說：
每個節點都有選擇類表，如果列表為空，則結束。否則依次DFS(x) , x $\in$ 選擇列表。節點中間的數字就是DFS序（時間戳）

某個節點為cur，它的任意祖先節點為anc，任意后代為pos。
深度優先有如下性質：
一，當DFS(cur)沒有開始執行時，DFS(pos)一定沒有開始執行。
二，當DFS(cur)執行結束時，DFS(pos)一定執行結束。
三，如果cur是長子節點，則DFS(cur)結束后。DFS(anc)正在執行，DFS(pos)已經執行結束。其它節點，都沒有開始執行。
四，當前節點，可能是后代節點的前置條件，比如： 求層次(leve)。后代節點也可能是當前節點的前置條件，如：求后代數量。
五，DFS(cur)時的DFS序為time1 ，結束時的DFS序為time2。 則DFS序為[time1,time2)的節點 $?$ cur及cur的后代。

經典應用

無向圖的DFS。需要cur節點parent，當next == parent 是忽略，否則無需循環{cur,parent,cur,parent$?$ }
有向圖，一般不需要，因為大部分情況是無環圖。

封裝類

枚舉

CEnumNeiBo 枚舉鄰接點，如果有環，以第一次訪問為準。CEnumChild 枚舉孩子、無環、無向圖。

class IDFSEnum
{
public:virtual void Enum(int cur, std::function<void(int)> fun) =0;virtual int NodeCount() = 0;virtual void Clear() = 0;};class CEnumNeiBo : public IDFSEnum
{
public:CEnumNeiBo(const vector<vector<int>>& vNeiBo) :m_vNeiBo(vNeiBo) {Clear();}virtual void Clear() override{ m_vVisit.assign(m_vNeiBo.size(), false); };
protected:virtual void Enum(int cur, std::function<void(int)> fun) override {m_vVisit[cur] = true;for (const auto& next : m_vNeiBo[cur]) {if (m_vVisit[next]) { continue; }fun(next);}}virtual int NodeCount() { return m_vNeiBo.size(); };const vector<vector<int>>& m_vNeiBo;vector<int> m_vVisit;
};class CEnumChild : public IDFSEnum
{
public:CEnumChild(const vector<vector<int>>& vChild) :m_vChild(vChild) {}
protected:virtual void Enum(int cur, std::function<void(int)> fun) override {for (const auto& next : m_vChild[cur]) {fun(next);}}virtual int NodeCount() { return m_vChild.size(); };virtual void Clear() override {};const vector<vector<int>>& m_vChild;
};

枚舉各節點的孩子

class CDFSChild
{
public:const vector<vector<int>>& DFSChild(IDFSEnum& dfsEnum, int root) {dfsEnum.Clear();m_vChild.resize(dfsEnum.NodeCount());DFS(dfsEnum, root);return m_vChild;};
protected:void DFS(IDFSEnum& dfsEnum, int cur) {dfsEnum.Enum(cur, [&](int next) {m_vChild[cur].emplace_back(next); DFS(dfsEnum, next); });}vector<vector<int>> m_vChild;
};

計算各節點層次

class CDFSLeve 
{
public:vector<int>& DFSLeve(IDFSEnum& dfsEnum,int root) {dfsEnum.Clear();m_vLeve.assign(dfsEnum.NodeCount(), -1);m_vLeve[root] = 0;DFS(dfsEnum,root);return m_vLeve;}
protected:void DFS(IDFSEnum& dfsEnum, int cur) {dfsEnum.Enum(cur, [&](int next) {m_vLeve[next] = m_vLeve[cur] + 1; DFS(dfsEnum, next); });	}vector<int> m_vLeve;
};

暴力計算樹直徑

class CDFSForDiameter 
{
public:int DFSDiameter(IDFSEnum& dfsEnum, int root) {dfsEnum.Clear();m_iRet = 1;DFS(dfsEnum, root);return m_iRet;}
protected:int m_iRet = 1;//記錄樹的直徑,0個節點的樹會出錯。int DFS(IDFSEnum& dfsEnum,int cur) {int left = 0;dfsEnum.Enum(cur, [&](int next) {auto right = DFS(dfsEnum,next);m_iRet = max(m_iRet, left + right + 1);left = max(left, right);});return left + 1;}
};

題解

無向樹路徑	難度分
【深度優先搜索】【圖論】【樹】2646. 最小化旅行的價格總和	2238
【圖論】【樹形dp】【深度優先搜索】2538. 最大價值和與最小價值和的差值	2397
【樹】【圖論】【樹路徑】【深度優先搜索】2867. 統計樹中的合法路徑數目	2428
C++深度優先搜索(DFS)算法的應用：2791樹中可以形成回文的路徑數	2677

無向圖	難度分
【深度優先搜索 圖論】：2925在樹上執行操作以后得到的最大分數	1939
【深度優先搜索】【樹】【圖論】2973. 樹中每個節點放置的金幣數目	2276
【圖論】【狀態壓縮】【樹】【深度優先搜索】1617. 統計子樹中城市之間最大距離	2308
C++深度優先(DFS)算法的應用：2920收集所有金幣可獲得的最大積分	2350
【樹】【異或】【深度優先】【DFS時間戳】2322. 從樹中刪除邊的最小分數	2391
【深度優先搜索】【樹】【C++算法】2003. 每棵子樹內缺失的最小基因值	2415
【樹】【因子數】【數論】【深度優先搜索】2440. 創建價值相同的連通塊	2460
【動態規劃】【樹形dp】【深度優先搜索】LCP 26. 導航裝置

有向圖	難度分
【歸并排序】【圖論】【動態規劃】【 深度優先搜索】1569將子數組重新排序得到同一個二叉搜索樹的方案數	2288
【深度優先】LeetCode1932:合并多棵二叉搜索樹	2483
【深度優先搜索】【樹】【有向圖】【推薦】685. 冗余連接 II

其它	難度分
【剪枝】【廣度優先】【深度優先】488祖瑪游戲
【深度優先搜索】【組合數學】【動態規劃】1467.兩個盒子中球的顏色數相同的概率	2356

擴展閱讀

視頻課程

有效學習：明確的目標 及時的反饋 拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

相關下載

想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結為主。
聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。