刷到熱題100的第437題時我一開始的想法很簡單這不就是在二叉樹上數(shù)路徑嗎結(jié)果動手一寫才發(fā)現(xiàn)這題和之前做過的“路徑總和”、“路徑總和II”完全不是一回事。路徑總和判斷的是“根節(jié)點到葉子節(jié)點”是否存在一條滿足條件的路路徑總和II還要你把路徑打印出來而437題的路徑起點和終點都是任意的只要沿著父節(jié)點到子節(jié)點的方向往下走任何一段連續(xù)路徑都算數(shù)。這種“任意起點、任意終點”的小改動直接把難度拉高了一檔。這篇文章我打算從最直觀的暴力解法開始講一步步過渡到面試官真正想聽的前綴和哈希表解法再把實現(xiàn)細(xì)節(jié)、邊界條件和容易踩的坑全部過一遍。無論你是剛開始刷二叉樹的新手還是已經(jīng)能把遞歸寫得行云流水的老手這篇文章應(yīng)該都能給你一點新的思考角度。1. 別被“路徑總和”這個名字騙了三道題的演進決定了這題的難度1.1 從“根到葉子”到“任意向下路徑”題意發(fā)生了質(zhì)變力扣里“路徑總和”系列一共有三道題我建議你按順序刷因為它們的難度是遞進的題目起點終點要求路徑總和根節(jié)點葉子節(jié)點判斷是否存在路徑總和II根節(jié)點葉子節(jié)點返回所有滿足條件的路徑路徑總和III任意節(jié)點任意后代節(jié)點統(tǒng)計滿足條件的路徑數(shù)量前兩道的路徑被限定得很死必須從根出發(fā)必須到葉子為止。所以它們的解法就是標(biāo)準(zhǔn)的先序遍歷走到葉子節(jié)點時判斷累加和是否等于目標(biāo)值。這里有個關(guān)鍵細(xì)節(jié)由于題目沒限制節(jié)點值和目標(biāo)值的正負(fù)實際上很多用例里含有負(fù)數(shù)你不能在累加和等于目標(biāo)值時提前返回必須走完整個分支才能確定答案。而437題的“任意起點”意味著什么意味著樹上的每一個節(jié)點都有資格成為某條合法路徑的起點。這樣一來原先那種“從根一路走到葉子”的單次遍歷就不夠了——你需要枚舉所有起點對每個起點再向下枚舉所有終點。這才是437題真正的難點所在。1.2 “任意起點”讓暴力解法的時間復(fù)雜度直接翻倍我畫個極端例子你就明白了。如果一棵樹是鏈狀結(jié)構(gòu)比如每個節(jié)點只有右孩子那么這棵樹退化成一條長度為n的鏈表。此時從第1個節(jié)點出發(fā)有n-1個可選終點從第2個節(jié)點出發(fā)有n-2個可選終點……總路徑數(shù)量是12...n也就是O(n^2)量級。即便是一棵平衡二叉樹起點數(shù)有n個每個起點向下延伸的平均深度也只有O(log n)左右總工作量是O(n log n)。這就是暴力和優(yōu)化的分水嶺暴力解法我們當(dāng)然要會寫它能幫助你驗證思路、跑通測試用例但面試時如果只給出暴力解法面試官基本上會接著問一句“能不能優(yōu)化到O(n)”。所以接下來的思路是先寫出暴力再理解為什么暴力慢最后搞清楚前綴和是怎么把復(fù)雜度降下來的。2. 暴力解法雙重DFS先把“能過”的方案寫出來2.1 核心思路外層枚舉起點內(nèi)層向下累加暴力解法的思路非常直接分成兩層遞歸外層遞歸負(fù)責(zé)枚舉路徑的起點。以當(dāng)前節(jié)點為起點時調(diào)用一個內(nèi)部函數(shù)從這個起點出發(fā)向下累加。內(nèi)層遞歸負(fù)責(zé)在固定起點的情況下向下擴展路徑每走到一個節(jié)點就判斷“從起點到當(dāng)前節(jié)點的路徑和”是否等于目標(biāo)值。如果等于計數(shù)加1。這里有一個容易和前面幾題混淆的點內(nèi)層遞歸中即使累加和已經(jīng)等于目標(biāo)值了也不能停止向下遍歷。比如目標(biāo)值是5一條路徑是5 - 0 - 0累加和第一次到達5時如果直接返回就會漏掉后面兩個同樣是5的終點。又比如10 - -5在10這個節(jié)點累加和還沒到5但加上后面的-5后剛好等于5。所以內(nèi)層遍歷必須走到葉子節(jié)點為止。寫成Java代碼就是下面這樣class Solution { public int pathSum(TreeNode root, int targetSum) { if (root null) { return 0; } // 以當(dāng)前節(jié)點為起點搜一遍 在左子樹里繼續(xù)枚舉起點 在右子樹里繼續(xù)枚舉起點 return rootSum(root, targetSum) pathSum(root.left, targetSum) pathSum(root.right, targetSum); } private int rootSum(TreeNode node, long targetSum) { if (node null) { return 0; } int count 0; if (node.val targetSum) { count; } // 注意這里不能用 node.val targetSum 就返回 count rootSum(node.left, targetSum - node.val); count rootSum(node.right, targetSum - node.val); return count; } }Python版本也順手貼出來邏輯完全一致class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - int: if root is None: return 0 return self.root_sum(root, targetSum) \ self.pathSum(root.left, targetSum) \ self.pathSum(root.right, targetSum) def root_sum(self, node: Optional[TreeNode], target_sum: int) - int: if node is None: return 0 count 1 if node.val target_sum else 0 count self.root_sum(node.left, target_sum - node.val) count self.root_sum(node.right, target_sum - node.val) return count2.2 為什么內(nèi)層遞歸用 targetSum - node.val 這種寫法很多同學(xué)第一次寫內(nèi)層遞歸時會習(xí)慣性地維護一個curSum每走到一個節(jié)點就curSum node.val然后判斷curSum targetSum。這種寫法沒問題但有一種更簡潔的等價寫法不要累加當(dāng)前和而是把目標(biāo)值不斷減去節(jié)點值。如果某個節(jié)點值等于剩余目標(biāo)值說明從起點到這里的路徑和正好等于原始目標(biāo)值。用targetSum - node.val的好處是省去了一個“當(dāng)前累計和”變量代碼更干凈也更容易看出遞歸的數(shù)學(xué)含義每往下走一步需要湊的差值就減少相應(yīng)節(jié)點值。不過如果為了和后面前綴和解法保持一致你也可以在內(nèi)部維護一個curSum沒有本質(zhì)區(qū)別。2.3 暴力的復(fù)雜度以及為什么OJ能過但面試可能會被追問暴力解法在最壞情況下時間復(fù)雜度是O(n^2)其中n是節(jié)點總數(shù)?？臻g復(fù)雜度是O(n)主要消耗在遞歸調(diào)用棧上——當(dāng)樹退化成鏈時遞歸深度最大可以達到n。在熱題100的測試數(shù)據(jù)里暴力解法其實是可以提交通過的畢竟題目限定的數(shù)據(jù)規(guī)模不算特別夸張。但如果你在面試中寫出了這個版本最好主動把復(fù)雜度分析說清楚然后告訴面試官這個解法能過是因為數(shù)據(jù)范圍允許但理論上還可以優(yōu)化到O(n)用前綴和哈希表來做。展現(xiàn)出這種“我會暴力但我知道怎么優(yōu)化”的狀態(tài)往往比只會背最優(yōu)解更能加分。3. 前綴和登場把樹上任意向下路徑變成兩個前綴和的差3.1 先回顧一維數(shù)組的最經(jīng)典做法和為K的子數(shù)組要理解437的最優(yōu)解繞不開一道更簡單的題給一個整數(shù)數(shù)組和一個目標(biāo)值K統(tǒng)計有多少個連續(xù)子數(shù)組的和等于K。這題的暴力做法是枚舉所有子數(shù)組O(n^2)。但有一個經(jīng)典優(yōu)化定義前綴和pre[i]表示數(shù)組前i個元素的和。那么從第i1個元素到第j個元素的連續(xù)子數(shù)組和等于pre[j] - pre[i]。要找和為K的子數(shù)組就是找滿足pre[j] - pre[i] K的(i, j)對也就是pre[i] pre[j] - K。具體實現(xiàn)時用一個哈希表記錄“當(dāng)前已經(jīng)出現(xiàn)過哪些前綴和、各出現(xiàn)多少次”。從頭掃描數(shù)組每次遇到pre[j]就去哈希表里查pre[j] - K出現(xiàn)了多少次這個次數(shù)就是以j結(jié)尾、且和為K的連續(xù)子數(shù)組個數(shù)。3.2 把樹的路徑對齊成前綴和之差樹結(jié)構(gòu)的路徑本質(zhì)上也是一個“連續(xù)區(qū)間”——只不過區(qū)間是從某個祖先節(jié)點延伸到某個后代節(jié)點。如果我們維護一個變量curSum表示從根節(jié)點到當(dāng)前遍歷到的節(jié)點的路徑和那么樹上任意一條向下路徑的和都可以用兩個這樣的前綴和相減得到。假設(shè)路徑的起點是節(jié)點p終點是當(dāng)前節(jié)點node那么路徑和等于curSum(node) - curSum(parent(p))。其中parent(p)表示p的父節(jié)點。如果p本身就是根節(jié)點那么parent(p)為空相當(dāng)于前綴和為0的空路徑。也就是說要判斷從某個祖先p到當(dāng)前節(jié)點node的路徑和是否等于targetSum只需要檢查curSum(parent(p))是否等于curSum(node) - targetSum。這聽起來有點繞但本質(zhì)和一維數(shù)組完全一樣。數(shù)組里是“前i個元素和”與“前j個元素和”之差樹里是“根到某個祖先的父節(jié)點”與“根到當(dāng)前節(jié)點”的前綴和之差。兩者的關(guān)鍵都落在想辦法快速查出所有滿足條件的前綴和。3.3 為什么樹上需要“回溯”而數(shù)組不需要數(shù)組是線性結(jié)構(gòu)從左到右掃過去每個前綴和全局共用所有歷史前綴和都可以保留。但樹是分叉結(jié)構(gòu)在左子樹里積累的前綴和記錄不能帶進右子樹。例如根節(jié)點有兩個子節(jié)點進入右子樹時如果哈希表里還留著左子樹某個節(jié)點的前綴和那么在查詢右子樹里的路徑時可能會錯誤匹配到左子樹的節(jié)點計算出根本不存在的路徑。所以樹上應(yīng)用前綴和套路時必須在遞歸返回的時候撤銷狀態(tài)。這就是“回溯”出現(xiàn)在這里的根本原因。你不需要背誦“這道題要回溯”只要想清楚“左右子樹的前綴和記錄必須互相隔離”自然就會在遞歸結(jié)束后刪除自己添加的記錄。一旦理解了這一點代碼基本不會寫錯。4. 回溯哈希表的完整實現(xiàn)正確性、代碼與三個必踩的坑4.1 先查再更新然后遍歷子樹最后回溯前綴和哈希表的實現(xiàn)核心就一句話每到一個節(jié)點先查“以當(dāng)前節(jié)點為終點的合法路徑有多少條”再把當(dāng)前節(jié)點的前綴和記錄進哈希表遍歷完左右子樹后刪除該記錄。完整Java代碼如下class Solution { private MapLong, Integer prefixMap new HashMap(); private long targetSum; public int pathSum(TreeNode root, int targetSum) { this.targetSum targetSum; // 這個0非常關(guān)鍵代表“空節(jié)點”的前綴和 prefixMap.put(0L, 1); return dfs(root, 0L); } private int dfs(TreeNode node, long curSum) { if (node null) { return 0; } curSum node.val; // 先查以當(dāng)前節(jié)點為終點起點上方的前綴和需要等于 curSum - targetSum int count prefixMap.getOrDefault(curSum - targetSum, 0); // 再更新把當(dāng)前前綴和記錄下來 prefixMap.put(curSum, prefixMap.getOrDefault(curSum, 0) 1); count dfs(node.left, curSum); count dfs(node.right, curSum); // 回溯撤銷當(dāng)前節(jié)點對后續(xù)兄弟子樹的影響 prefixMap.put(curSum, prefixMap.get(curSum) - 1); return count; } }Python版本from collections import defaultdict class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - int: prefix defaultdict(int) prefix[0] 1 self.target_sum targetSum self.ans 0 def dfs(node: Optional[TreeNode], cur_sum: int) - None: if node is None: return cur_sum node.val self.ans prefix[cur_sum - self.target_sum] prefix[cur_sum] 1 dfs(node.left, cur_sum) dfs(node.right, cur_sum) prefix[cur_sum] - 1 dfs(root, 0) return self.ans代碼量很少但正確性推理值得展開說說假設(shè)當(dāng)前節(jié)點是nodecurSum是根到node的路徑和。任何一條以node為終點的合法路徑都對應(yīng)著一個起點p使得curSum(node) - curSum(parent(p)) targetSum也就是curSum(parent(p)) curSum(node) - targetSum。到達node時哈希表里存儲的是“根到node這條路徑上所有節(jié)點包括根節(jié)點的虛擬父節(jié)點的前綴和出現(xiàn)次數(shù)”所以prefixMap[curSum - targetSum]的值就是所有以node為終點、且路徑和等于targetSum的路徑數(shù)量。因為每條路徑只有一個終點按終點分類統(tǒng)計每個路徑恰好被計入一次不會重復(fù)也不會遺漏。4.2 三個必踩的坑第一個坑是最經(jīng)典的哈希表里漏了put(0L, 1)。這個初始鍵值代表“根節(jié)點之前的空路徑前綴和”。如果沒有它所有從根節(jié)點出發(fā)的合法路徑都會被漏掉。舉個例子一棵樹只有一個根節(jié)點值等于targetSum沒有0 - 1這個初始記錄查詢時prefixMap[curSum - targetSum]查到的是prefixMap[0]結(jié)果是0正確答案1就沒了。新手很容易在這里翻車。第二個坑是更新順序。必須先查再更新不能先更新再查。如果targetSum恰好等于0先更新的話當(dāng)前節(jié)點的前綴和curSum被記錄下來緊接著查詢prefixMap[curSum - 0]就會把自己剛加入的記錄也算進去導(dǎo)致多計一條“從當(dāng)前節(jié)點到當(dāng)前節(jié)點且和為0”的路徑。這看起來像是正確的單個節(jié)點路徑和確實可以是0但前提是節(jié)點值本身為0而不是用curSum去湊實際上會造成系統(tǒng)性錯誤。第三個坑是忘記回溯。很多同學(xué)寫遞歸時記得進入子樹前更新狀態(tài)卻忘了遞歸返回后恢復(fù)狀態(tài)。這導(dǎo)致左子樹的前綴和記錄污染右子樹的查詢結(jié)果。我自己的習(xí)慣是寫完遞歸調(diào)用之后立刻檢查一遍看有沒有需要“撤銷”的操作寧可先寫一個prefixMap.put(curSum, prefixMap.get(curSum) - 1)也不要在出問題時再回來補。4.3 為什么用long而不是int題目里單節(jié)點值范圍看似安全但路徑和是沿途所有節(jié)點值的累加。當(dāng)樹高較大、節(jié)點值全是負(fù)數(shù)或全是正數(shù)時累加和很容易超出int范圍在做減法時還可能帶來溢出異常。所以無論是暴力版本還是前綴和版本建議直接把前綴和類型聲明為long。這在面試中也是一個能體現(xiàn)經(jīng)驗的細(xì)節(jié)。5. 邊界用例與復(fù)雜度從“能過”到“所有情況都對”5.1 這些測試用例一定要自己過一遍寫完之后先別急著提交手推幾個邊界場景空樹root為null路徑數(shù)量為0。前綴和解法里dfs(root, 0)直接返回0。單節(jié)點樹節(jié)點值為targetSum答案是1否則是0。targetSum為0的樹這最容易出錯。如果每個節(jié)點的值不為0但路徑上正負(fù)值相消也能湊出很多路徑。此時前綴和里keycurSum和curSum - 0相等尤其要注意查詢順序。全負(fù)數(shù)節(jié)點同樣能構(gòu)成合法路徑。暴力解法中不能因為當(dāng)前累加和已經(jīng)小于目標(biāo)值就剪枝負(fù)數(shù)會繼續(xù)拉低累加和。我自己常用的驗證方式是構(gòu)造一個結(jié)構(gòu)簡單的樹用暴力法和前綴和法同時跑比對結(jié)果。比如下面這棵樹targetSum11 / \ 2 -3 / \ 3 1手?jǐn)?shù)答案路徑1根節(jié)點本身1條路徑2 - 1第二條路徑累加和3不對路徑1右子樹葉子節(jié)點本身1條路徑-3 - 1根到右子樹葉子累加和-2不對路徑1 - 2 - 3累加和6不對路徑2 - 35不對路徑1左子樹右葉子1條。正確答案是2。這個用例能幫你同時檢查暴力遞歸和前綴和邏輯。5.2 復(fù)雜度細(xì)節(jié)對比前綴和解法每個節(jié)點只會被訪問一次每次訪問只做常數(shù)次哈希表操作時間復(fù)雜度是O(n)?？臻g復(fù)雜度主要由遞歸棧深度和哈希表大小決定最壞情況下樹退化成鏈遞歸深度O(n)哈希表存了n個不同前綴和總共O(n)。平衡樹情況下遞歸深度O(log n)哈希表長度還是O(n)總體依然是O(n)空間。對比一下暴力解法解法時間復(fù)雜度空間復(fù)雜度適用性雙重DFS最壞O(n^2)平衡樹O(n log n)O(n)數(shù)據(jù)規(guī)模小思路直白前綴和哈希表O(n)O(n)標(biāo)準(zhǔn)最優(yōu)解面試推薦可以看出前綴和解法不僅在時間上有優(yōu)勢代碼結(jié)構(gòu)也足夠清晰面試時優(yōu)先寫這一版更穩(wěn)妥。5.3 從“過用例”到“過邊界”的檢查順序我平時提交前會按這個順序自我檢查先檢查空樹再檢查根節(jié)點單節(jié)點然后構(gòu)造一條鏈狀樹驗證遞歸深度不會爆棧最后構(gòu)造一個含有正負(fù)數(shù)且目標(biāo)值為0的樹驗證查詢順序和回溯邏輯。特別是目標(biāo)值為0的情況用三個節(jié)點值為1, -1, 1的鏈狀樹手算一遍能迅速暴露“先更新后查詢”的錯誤。6. 舉一反三前綴和哈希表還能解決哪些同類題6.1 回顧經(jīng)典變式一維連續(xù)子數(shù)組求和前綴和哈希表最原始的形態(tài)就是“和為K的連續(xù)子數(shù)組數(shù)量”。把樹的路徑問題理解成一維問題的“樹上版本”之后你會發(fā)現(xiàn)兩道題的配對數(shù)表幾乎一模一樣唯一區(qū)別就是樹遍歷需要回溯數(shù)組遍歷不需要。如果拿這兩道題一起刷收獲會非常大。刷題時遇到“連續(xù)子數(shù)組”、“連續(xù)子序列”、“向下路徑”這類字眼先想想能不能用前綴和套路。6.2 如果題目改成“打印所有滿足條件的路徑”怎么辦有些公司面試會在437基礎(chǔ)上加一個要求不僅要統(tǒng)計數(shù)量還要把所有路徑打印出來。這時候前綴和哈希表就有點力不從心了因為哈希表只存次數(shù)不存具體位置。一個可行方案退回到DFS維護一條“從根到當(dāng)前節(jié)點”的路徑列表每進入一個節(jié)點從當(dāng)前路徑的末尾向前遍歷枚舉所有以當(dāng)前節(jié)點為終點的子路徑滿足條件就記錄。由于要輸出路徑本身復(fù)雜度至少是O(n^2)量級因為輸出數(shù)量本身可能就有這么多這和統(tǒng)計數(shù)量問題有本質(zhì)區(qū)別。在面試中遇到這種擴展一定要先說清楚“如果需要輸出具體路徑復(fù)雜度無法避免地會變高”。6.3 二維矩陣前綴和也是同一套思想再往外延伸一點二維矩陣中求子矩陣和為target的問題也可以用二維前綴和預(yù)處理再對每一行區(qū)間枚舉列邊界配合哈希表降到O(m * n^2)或更好。這個思路和一維情形一脈相承只是細(xì)節(jié)更多。真正理解“前綴和之差 區(qū)間和”這個等式后從數(shù)組到樹再到矩陣都是同一套底層邏輯。6.4 我建議的練習(xí)順序不要一上來就背最優(yōu)解。先按“暴力DFS - 發(fā)現(xiàn)復(fù)雜度問題 - 推前綴和思路 - 手寫前綴和代碼 - 驗證邊界”的順序走一遍。這個過程走下來你會對遞歸、回溯、狀態(tài)管理有很具體的體感而不是停留在背模板。等遇到其他變形題時至少知道往哪個方向想。我個人在寫這類題時還有一個習(xí)慣在紙上把樹畫出來把每個節(jié)點的“根到該節(jié)點的前綴和”標(biāo)在旁邊。標(biāo)完之后你會發(fā)現(xiàn)任意兩個節(jié)點之間的路徑和就是它們前綴和之差整棵樹的信息一下就清晰了。437這道題之所以能成為熱題100里的?？途褪且驗樗选扒熬Y和、哈希表、回溯、遞歸”四個高頻考點全揉在了一起一道題吃透相當(dāng)于同時復(fù)習(xí)了二叉樹和數(shù)組兩類經(jīng)典套路。