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