算法奇妙屋寫到第二十六期終于輪到二叉樹里最容易被初學者“背會模板卻沒理解靈魂”的深度優(yōu)先搜索了。不管你是剛接觸遞歸的算法新手還是刷題準備面試的老手二叉樹的DFS都是繞不開的主場。這篇文章不講花哨技巧我會直接從DFS的本質、三種遍歷順序的記憶方式、幾類高頻題型的統(tǒng)一解法以及遞歸的隱藏問題這幾個角度一次性把這塊內(nèi)容拆透。很多人覺得二叉樹DFS就是“前序中序后序背一背遞歸三行代碼一把梭”但真遇到改寫成迭代、遇到返回值的語義設計、遇到遞歸棧溢出時就露餡了。我寫這篇的目的就是讓你在看完之后不只是會寫代碼而是能像設計一個遞歸任務一樣去設計DFS函數(shù)。1. 為什么二叉樹的DFS無法回避問題結構本身就決定了解法1.1 深度優(yōu)先搜索是二叉樹天然的任務模型先想一個問題為什么二叉樹問題里DFS這么多見因為二叉樹本身就是一種“遞歸定義”的數(shù)據(jù)結構。一棵樹的左子樹和右子樹還是樹。這意味著你天然可以站在任意一個節(jié)點上把“處理整棵樹”的任務拆成“處理當前節(jié)點”和“處理兩棵子樹”兩個子任務。而這種“把任務分解到子樹再逐步深入”的推進方式恰好就是深度優(yōu)先搜索的路線沿著一條分支深入到葉子再回頭走另一條分支。廣度優(yōu)先搜索BFS走的是“逐層掃描”適合找最短路徑、做層級相關的輸出。而DFS走的是“先到底再回溯”在需要“判斷某個路徑是否存在”“在葉子節(jié)點附近做判斷”“理解節(jié)點之間的祖先關系”這類場景里表達起來更自然。可以說二叉樹的存儲結構就是用遞歸定義的那么用遞歸的DFS去處理它是信息損失最少的方式。1.2 一個遞歸調用就是一個完整的小任務我見過不少同學理解DFS時卡在“遞歸到底是怎么一層一層回來的”這個問題上然后開始畫很復雜的箭頭圖。其實換個方式想好得多遞歸函數(shù)就是一個“做完整件事”的函數(shù)。你調用它處理左子樹它就會把左子樹徹底處理好再交回給你。你不需要在意它中間經(jīng)歷了什么細節(jié)你只需要相信它接受一個節(jié)點作為參數(shù)就會把這個節(jié)點以及它的所有后代處理完。以“求二叉樹最大深度”為例你站在當前節(jié)點上完成“當前這一步”的動作。然后把這個節(jié)點交給遞歸函數(shù)去處理左子樹獲得左子樹深度。再把右子樹交給遞歸函數(shù)獲得右子樹深度。最后你合成結果。這個模型叫“相信遞歸”在寫函數(shù)體的時候先把遞歸調用公式寫在紙上確定“如果子樹已經(jīng)被處理好了我該怎么得到當前節(jié)點的結果”。這一步通了整道題就通了。1.3 三個問題快速判斷該在前中后哪里動代碼每個節(jié)點都會被訪問三次剛進入時是一次機會處理完左子樹回來是一次機會處理完右子樹回來是最后一次機會。你的業(yè)務代碼寫在哪一次機會上就決定了遍歷順序。所以判斷DFS某個變體只需要問自己我需要先拿到左右子樹的信息再決定當前節(jié)點的結果嗎——如果是用后序。我需要在進入子樹之前就處理當前節(jié)點嗎——如果是用前序。需要讓左子樹的結果和當前節(jié)點一起構成某種順序輸出嗎——如果是用中序。舉個實際例子判斷一棵樹是不是二叉搜索樹。二叉搜索樹的中序遍歷結果必須單調遞增所以在中序位置去做“前一個值是否小于當前值”的檢查比前序后序都直觀。這就是“選擇代碼位置”的典型案例。2. 一套模板三處擺位前中后序的實質和記憶方法2.1 遞歸遍歷的“骨架代碼”想把前中后序一次記牢就得統(tǒng)一一套框架不要每道題臨時想函數(shù)簽名。最穩(wěn)的模板是def dfs(node): if node is None: return # 位置A前序遍歷代碼 dfs(node.left) # 位置B中序遍歷代碼 dfs(node.right) # 位置C后序遍歷代碼你把“處理當前節(jié)點”的代碼放在A就是前序放在B就是中序放在C就是后序。這不是什么高深技巧但它能幫你在面試時快速寫出任意順序的遍歷。同時這個框架也暗示了一個重要的事實前中后序的區(qū)別只取決于“當前節(jié)點業(yè)務代碼”在遞歸調用之間的擺位而不在于遞歸本身的復雜度。2.2 三種順序的直觀含義前序遍歷的順序是“當前節(jié)點 → 左子樹 → 右子樹”。它適合做樹的拷貝、序列化、或者需要在進入子樹前就記錄路徑的場景。因為它先訪問根你能在“往深處走”的第一時間保存祖先信息。中序遍歷的順序是“左子樹 → 當前節(jié)點 → 右子樹”。對于一棵二叉搜索樹中序遍歷的結果就是遞增序列。這個順序最常見的應用就是“驗證二叉搜索樹”“BST轉有序鏈表”這類問題。后序遍歷的順序是“左子樹 → 右子樹 → 當前節(jié)點”。它的特點是當前節(jié)點的值計算依賴左右子樹的結果。求樹的高度、判斷平衡、計算路徑和由子樹累加得到這類需要“匯總子問題”的問題幾乎都走后序。2.3 一個類比幫你記住擺位你可以把二叉樹DFS當成一次“匯報任務”。前序是“領導先講話再聽下屬匯報左部門再聽右部門”中序是“先聽左部門匯報領導講話再聽右部門”后序是“兩個部門都匯報完了領導再做總結”。在面試中如果一時記混心里默念一遍這個匯報場景基本就能判斷該把代碼放在哪。尤其是后序左右子樹的結果都返回了才輪到當前節(jié)點綜合處理這幾乎是一年以后寫樹形DP題的核心思維。3. 高頻DFS題型的統(tǒng)一套路從最大深度到最近公共祖先3.1 四步設計一個DFS函數(shù)我梳理過很多二叉樹DFS題發(fā)現(xiàn)只要會了下面這四步絕大多數(shù)題都不會出現(xiàn)“毫無頭緒”的狀態(tài)確定遞歸函數(shù)的輸入和返回值。輸入一般是當前節(jié)點返回值根據(jù)業(yè)務定義。寫遞歸邊界。通常是節(jié)點為空時返回什么偶爾是葉子節(jié)點時單獨處理。在左子樹和右子樹上遞歸調用。根據(jù)左右子樹的結果合成當前節(jié)點的返回結果。以“最大深度”為例def max_depth(root): if root is None: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1遞歸邊界空節(jié)點深度為0。合成邏輯當前節(jié)點深度 左右子樹最大深度 1。就這么簡單。這道題的代碼是很多“后序型DFS”的模板來源。3.2 路徑總和需要帶著累計狀態(tài)深入路徑總和是“前序型DFS”的典型。它要求在進入子樹時攜帶當前已經(jīng)累加的路徑和并在葉子節(jié)點判斷是否等于目標值def has_path_sum(root, target_sum): if root is None: return False target_sum - root.val if root.left is None and root.right is None: return target_sum 0 return has_path_sum(root.left, target_sum) or has_path_sum(root.right, target_sum)這里的技巧是把target_sum逐層減去當前節(jié)點的值而不是在遞歸里再傳一個累加變量。這讓函數(shù)簽名更干凈。葉子節(jié)點的判斷放在左右子樹的遞歸調用之前因為當前這層的目標值已經(jīng)扣掉了當前節(jié)點的貢獻。3.3 最近公共祖先理解后序返回值的“雙層含義”最近公共祖先LCA是二叉樹DFS里最值得吃透的一道題因為它同時檢驗你對“返回值設計”和“后序語義”的理解。def lowest_common_ancestor(root, p, q): if root is None: return None if root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right這個返回值是“當前子樹中p或q是否已經(jīng)找到”的合并結果。如果左子樹返回非空說明左子樹里找到了p或q之一右子樹同樣。當左右都非空說明當前節(jié)點就是第一個同時連接p和q的祖先即最近公共祖先。我第一次做這道題時也卡了很久后來發(fā)現(xiàn)關鍵在于返回值不一定表示“答案”而是表示“有沒有找到目標節(jié)點”最終答案由邏輯判斷組合出來。這種“返回值語義”的思考方式是很多中等難度DFS題的核心。3.4 套路的適用范圍這套四步法也不是所有題都適用。它的強項是“單棵樹上做后序聚合”和“帶狀態(tài)深入”這兩大類。真正需要跳出這個框架的往往是需要在DFS過程中配合全局變量、或者需要回溯修改狀態(tài)的問題。但即便如此遞歸邊界和遞歸調用的寫法依然是相通的。4. 遞歸不是萬能的棧溢出、重復計算與迭代改寫4.1 遞歸深度上限你以為的最大深度可能撐不到很多人在學習DFS時忽略了一個工程問題遞歸深度。Python默認遞歸深度是1000層左右Java、C的?？臻g也有限。當二叉樹退化成鏈狀每個節(jié)點只有一個子節(jié)點樹的深度等于節(jié)點數(shù)量此時遞歸寫法會直接導致棧溢出。平時的刷題用例里樹不會特別大但等到處理真實數(shù)據(jù)或者面試官故意構造退化樹時遞歸DFS就會翻車。所以要養(yǎng)成習慣先估算樹的深度范圍。如果深度可能超過1000就要提前考慮迭代寫法。舉一個直觀的對比方案遞歸DFS顯式棧迭代DFS代碼可讀性高貼近數(shù)學表達中低需要管理棧狀態(tài)?？臻g使用調用棧深度受限使用堆內(nèi)存容量更大調試難度需要跟蹤調用鏈需要跟蹤棧內(nèi)狀態(tài)適合場景樹深度可控的常規(guī)題深度可能極大的工程場景4.2 記憶化DFS二叉樹里什么時候真的需要DFS的一個經(jīng)典優(yōu)化是“記憶化”即把已經(jīng)算過的狀態(tài)存起來避免重復計算。但是在普通二叉樹上由于每個節(jié)點只能通過唯一的父節(jié)點路徑到達DFS天然不會重復訪問同一個節(jié)點記憶化通常沒有意義。什么時候有用兩種場景樹上存在多重路徑指向同一個“邏輯狀態(tài)”的DP問題。遞歸展開時左側分支和右側分支會大量覆蓋相同的子樹場景。典型的例子是“打家劫舍 III”這類樹形DP題。雖然它也是二叉樹DFS但不同解法之間可能在同一個節(jié)點上重復計算多次用緩存能顯著減少時間。所以在使用記憶化之前先問自己同一個節(jié)點會被以不同路徑訪問兩次以上嗎會才需要哈希表不會就是畫蛇添足。4.3 用顯式棧模擬遞歸的正確思路迭代改寫DFS最常規(guī)的寫法是用棧保存“待訪問節(jié)點”前序版本非常直觀def preorder_traversal(root): stack [] result [] if root: stack.append(root) while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result注意壓棧順序棧后進先出所以先壓右子樹再壓左子樹彈出時才是“先左后右”。后序和迭代中序則需要額外標記位或雙棧邏輯會復雜不少。我的建議迭代寫法不需要每種都死記前序迭代必須會寫因為它最常用中序后序理解思路即可真遇到了現(xiàn)推也來得及。4.4 什么時候“放棄遞歸”反而更劃算如果只是遍歷整棵樹做統(tǒng)計迭代寫法的收益主要體現(xiàn)在回避棧溢出。但如果DFS過程需要保留路徑回溯比如“求二叉樹所有根到葉子的路徑”顯式棧就需要額外存一份路徑狀態(tài)代碼會變得很繞此時我建議還是用遞歸加回溯。另外在“找目標路徑”“判斷是否存在某條路徑”這類場景中遞歸版本寫起來天然清晰沒必要為了“工程化”而刻意迭代。真正的取舍標準是樹的深度上限是否超出遞歸承受范圍。沒超出用遞歸可讀性優(yōu)先超出了再考慮顯式棧。5. 實戰(zhàn)排錯遞歸函數(shù)返回值抓狂時的排查鏈路5.1 癥狀一輸出明明對但提交超時或棧溢出先看遞歸邊界是不是漏了“空節(jié)點返回”。漏了邊界程序會在訪問root.left時嘗試訪問空指針這是最常見的崩潰來源。再檢查是否有“環(huán)路”如果數(shù)據(jù)結構里出現(xiàn)環(huán)引用例如測試數(shù)據(jù)構造了循環(huán)指向DFS就會無限遞歸。真遇到這種情況可以加一個節(jié)點訪問集合在進入遞歸前判斷是否已訪問過。雖然二叉樹理論無環(huán)但工程實踐里不排除異常數(shù)據(jù)。5.2 癥狀二返回值類型對不上最典型的是None和0混用我在帶新手的時候發(fā)現(xiàn)很多人寫“是否存在某種路徑”的題時喜歡把返回值設成布爾值但邊界返回了None。這會導致left or right這類邏輯表達式結果不是True/False而是一堆None程序看起來沒報錯結果卻是錯的。排查方法很簡單在每個return處打印返回值。如果發(fā)現(xiàn)“沒有目標卻返回了非None”十有八九是邊界條件寫錯了。建議所有需要布爾返回的DFS函數(shù)顯式return True或return False不要依賴return a or b的隱式轉換哪怕它有時候能用。5.3 癥狀三整棵樹都算錯但單步跟蹤心算沒問題這種通常不是語法錯而是“遞歸調用的位置擺錯了”。一個很經(jīng)典的例子想統(tǒng)計二叉樹節(jié)點個數(shù)卻把count 1 count(root.left) count(root.right)寫成了先遞歸再返回統(tǒng)一值導致漏算了部分子樹。這種問題只靠眼睛看很難發(fā)現(xiàn)我的經(jīng)驗是兩種方法結合第一構造節(jié)點數(shù)很少的樹單節(jié)點、兩層樹手工走一遍遞歸過程。第二在每個層級用縮進打印當前節(jié)點值類似print( * depth str(node.val))能直觀看到遞歸訪問順序是否符合預期。5.4 一個實用的最小測試集不管改遞歸函數(shù)還是迭代函數(shù)我都建議準備這么一組測試用樹空樹root None驗證邊界。單節(jié)點樹驗證返回值基準。只有左子樹的鏈狀樹驗證遞歸深度應對。完全二叉樹驗證左右子樹協(xié)調邏輯。目標值在深處的特殊樹驗證路徑類題目。尤其是“只有左子樹的鏈狀樹”它能同時檢驗遞歸深度、返回方向、左右子樹順序三個點。如果這道用例過了大部分DFS邏輯問題都能暴露出來。5.5 調試時的核心心態(tài)改遞歸代碼時不要試圖“人腦模擬所有遞歸層”真的會暈。正確處理方式是小規(guī)模草稿紙手算兩層確認邏輯大規(guī)模問題就加日志輸出縮小到可疑的那一層實在不行用迭代寫一個等價版本打印對比結果。對DFS這類問題調試效率最高的工具永遠是“最小用例 日志”而不是無腦斷點。寫在最后我解DFS題的一點習慣刷了這么多二叉樹題目我最深的體會是DFS不是一個需要“背模板”的知識點而是一個需要“先定返回值語義、再定代碼位置”的思維過程。拿到任何一道樹的題目我先不問“這是不是DFS題”而是先問自己三個問題我需要在子樹處理之前還是之后匯總信息返回值表示的是“答案”還是“搜索狀態(tài)”如果樹特別深我換迭代寫法是否還順手這二十多篇算法系列寫下來二叉樹的這部分內(nèi)容是讓我覺得數(shù)學模型和代碼結合得最舒服的一類。如果你正在刷題我建議你花一天時間只做“最大深度、路徑總和、最低公共祖先、二叉樹展開為鏈表”這四道題把它們的遞歸調用過程用日志打印出來看一遍?？疵靼啄菐讖埲罩据敵瞿阍倏慈魏味鏄涞腄FS題都會覺得那些解法是“順理成章”的而不是需要背的。