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