化)
第十五天的題單一拉出來我第一反應(yīng)是“這四道題都不難”?？烧鎰邮炙⑼瓴虐l(fā)現(xiàn)它們湊在一起是有講究的110、257、404、222幾乎把二叉樹遞歸里最核心的幾件事——后序求高度、前序收集路徑、用父節(jié)點視角判斷特殊節(jié)點、利用完全二叉樹特性優(yōu)化——各出了一道代表題。如果你也在跟代碼隨想錄算法訓練營刷二叉樹這一天值得停下來多琢磨一會兒別急著追求AC數(shù)量把這四道題的“為什么”吃透后面寫回溯和遞歸會順手很多。1. 第十五天的四道題正好湊齊二叉樹遞歸的三種套路1.1 一天的題單難度梯度其實很講究先說結(jié)論這四道題按難度排大概是 404 257 ≈ 110 222。但難度并非唯一線索更重要的是它們在遞歸思路上剛好互補。110平衡二叉樹要求你從子樹返回高度本質(zhì)是后序遍歷左-右-中因為必須先知道左右子樹的高度才能判斷當前節(jié)點是否平衡。257二叉樹的所有路徑要求從根走到葉子邊收集邊記錄本質(zhì)是前序遍歷中-左-右因為路徑的順序天然是從根開始的。404左葉子之和看起來簡單但真正的坎在于“左葉子”這個定義本身——它必須靠父節(jié)點來判定這是很多新手繞不過去的彎。222完全二叉樹的節(jié)點個數(shù)如果只求暴力解一兩分鐘就能寫出來可一旦想到“完全二叉樹”四個字你就應(yīng)該停下來想一想能不能利用滿二叉樹的數(shù)學性質(zhì)把復(fù)雜度從 O(n) 降到 O(log^2 n)。所以這一天的題單相當于把二叉樹遞歸里的三種“手感”都練了一遍求值用后序、收集路徑用前序、特性利用靠觀察和數(shù)學推導。這四道題我強烈建議不要只看題解自己先寫一版再對照優(yōu)化版收獲會翻倍。1.2 適合誰來讀讀之前需要什么基礎(chǔ)這篇復(fù)盤適合正在刷二叉樹、但還處在“每次遞歸都要重新想一遍”階段的讀者。如果你能區(qū)分先序/中序/后序的區(qū)別、能寫出遞歸版前序遍歷那么接下來的內(nèi)容你完全吃得下。如果你連遞歸都還有些發(fā)怵也沒關(guān)系我會先把每道題的遞歸三步曲拆開講清楚。刷二叉樹題目我一直堅持一個理念不要背題要背“套路”。樹這類結(jié)構(gòu)天生適合遞歸因為樹的子樹還是樹。而遞歸的難點從來不在“怎么寫”而在“這個函數(shù)該返回什么、什么時候停下來、單層邏輯做什么”。這四道題恰好就是把這三個問題分別放大給你看。2. 110. 平衡二叉樹先分清高度和深度后序遞歸才不會亂2.1 題目在考什么一顆樹到底怎么算“平衡”力扣 110 的平衡二叉樹定義每個節(jié)點的左右子樹高度差絕對值不超過 1。網(wǎng)上很多題解寫得很隨意但這里有個概念陷阱就是“高度”和“深度”經(jīng)常被混著用。我自己的記憶方法是深度是往下的從根到你所在節(jié)點高度是往上的從你所在節(jié)點到葉子。所以根節(jié)點的深度最大葉子節(jié)點的深度最小反過來葉子節(jié)點的高度最小約定為 1根節(jié)點的高度是整棵樹的最大深度。判斷一顆樹是否平衡邏輯上需要先知道左右子樹各自有多高再比較差值。這意味著在遞歸返回時你必須要得到“這棵子樹到底有多高”這個數(shù)字。如果某個子樹已經(jīng)不平衡了還需要繼續(xù)算它的高度嗎不需要直接向上傳遞一個“失敗信號”讓整棵樹提前結(jié)束。這個題目最容易犯的錯誤是想著“在每個節(jié)點用前序遍歷求它的深度再比較左右孩子深度的差”。這個思路看著對但實際上你求出來的“深度”并不是該節(jié)點子樹的高度而且每到一個節(jié)點都重新向下數(shù)一遍深度會帶來大量重復(fù)計算。正確姿勢只有一個用后序遍歷求高度。2.2 遞歸三部曲落地用-1既當高度又當失衡標記遞歸不管多繞先想三件事參數(shù)和返回值是什么、終止條件是什么、單層邏輯做什么。這道題我要返回高度但還要額外表達“這顆子樹已經(jīng)不平衡了”。兩個信息合并我的返回值就用一個 int正常情況返回高度一旦發(fā)現(xiàn)不平衡就返回 -1。這樣上層節(jié)點拿到 -1 后立刻就能判斷出整棵樹已經(jīng)不平衡沒必要再往下朝右子樹遞歸了。class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) ! -1; } private int getHeight(TreeNode node) { if (node null) { return 0; // 空節(jié)點高度為0 } int leftHeight getHeight(node.left); if (leftHeight -1) { return -1; // 左子樹已經(jīng)不平衡 } int rightHeight getHeight(node.right); if (rightHeight -1) { return -1; // 右子樹已經(jīng)不平衡 } // 當前節(jié)點的平衡性左右高度差不能超過1 if (Math.abs(leftHeight - rightHeight) 1) { return -1; } // 返回當前節(jié)點作為根的子樹的真實高度 return Math.max(leftHeight, rightHeight) 1; } }這段代碼建議親手抄一遍再默寫一遍。注意最后一行是Math.max(left, right) 1不是Math.min。這個 1 代表把當前節(jié)點自己也算進高度里這是整段遞歸字數(shù)最少卻最容易出錯的地方。2.3 提前返回的剪枝效果別把明明不平衡的子樹繼續(xù)算下去遞歸版里連續(xù)兩個if (leftHeight -1) return -1;看起來多此一舉實際是剪枝的精髓。我刷題時一開始偷懶省略了這兩個判斷心想反正最后Math.abs也會發(fā)現(xiàn)不平衡。但仔細一想如果左子樹已經(jīng)返回 -1說明左子樹內(nèi)部已經(jīng)失衡這時候繼續(xù)算右子樹的高度沒有任何意義純屬浪費時間。極端一點的情況是這樣一顆樹根節(jié)點的左子樹嚴重失衡而右子樹是節(jié)點數(shù)量極大的完全二叉樹。如果不剪枝左子樹發(fā)現(xiàn)失衡后代碼還要去把右子樹完整遍歷一遍白白花費 O(n) 時間剪枝后左子樹返回 -1 的那一剎那整個遞歸就一路向上退出右子樹根本不會被訪問到。這種“短路求值”思想在后面的回溯剪枝、動態(tài)規(guī)劃優(yōu)化里會反復(fù)出現(xiàn)越早習慣越省力。2.4 迭代思路能懂更好不懂也不影響做題遞歸版已經(jīng)足夠應(yīng)付面試和筆試但面試官偶爾會追問一句“你能用迭代寫嗎”。迭代思路其實是用顯式棧模擬后序遍歷同時用一個哈希表記錄每個節(jié)點的高度?；咎茁肥莾蓪拥谝粚佑脳ＤM“左-右-中”的后序訪問順序。遍歷到中間節(jié)點時先不斷把左孩子、右孩子壓棧確保左右子樹都處理完了才輪到中間節(jié)點。第二層每個中間節(jié)點出棧時從哈希表里查詢左右子樹的高度比較差值然后把當前節(jié)點的高度Math.max(left, right) 1存進哈希表。我在這里不放完整迭代代碼因為后序迭代本身比較繞很容易把初學者整懵。如果你目前還在建立遞歸直覺優(yōu)先吃透遞歸版等遞歸版熟練了再看迭代作為思維擴展。面試中能寫出簡潔遞歸并解釋清楚剪枝邏輯已經(jīng)能拿不錯的分數(shù)。3. 257. 二叉樹的所有路徑前序遍歷收集路徑遞歸返回時記得撤銷3.1 為什么一定要前序遍歷257 題要求返回所有從根到葉子的路徑比如[1-2-5, 1-3]。路徑的起點永遠是根順序永遠是“根在左、葉子在右”所以遍歷順序天然就是先訪問根再訪問左孩子再訪問右孩子也就是前序遍歷。中序和后序遍歷都會把根節(jié)點留在中間或最后處理你想按“從根到葉子”的順序拼接路徑還得額外處理字符串順序非常別扭。這也是一個判斷經(jīng)驗看到“從根到葉子”這種強依賴順序的需求優(yōu)先想前序遍歷。3.2 兩種實現(xiàn)String的天然回溯 與 StringBuilder的顯式回溯這道題最直觀的寫法是遞歸時傳一個 String因為 Java 的 String 是不可變的每次拼接都會生成新對象天然幫你“隔離”了路徑污染。class Solution { public ListString binaryTreePaths(TreeNode root) { ListString result new ArrayList(); if (root null) { return result; } dfs(root, , result); return result; } private void dfs(TreeNode node, String path, ListString result) { // 到達葉子生成一條完整路徑 if (node.left null node.right null) { result.add(path node.val); return; } String nextPath path node.val -; if (node.left ! null) { dfs(node.left, nextPath, result); } if (node.right ! null) { dfs(node.right, nextPath, result); } } }這種寫法的優(yōu)點是思路清晰新手也好懂缺點是每層遞歸都會新建字符串在節(jié)點數(shù)量很大的場景下會有一定開銷。但算法訓練階段先跑通邏輯比摳性能重要。用可變對象就得小心了。拿 StringBuilder 舉例由于它是可變的遞歸返回后如果不手動“撤銷”剛才追加的內(nèi)容左子樹殘留的路徑片段會污染右子樹的拼接結(jié)果。private void dfs(TreeNode node, StringBuilder sb, ListString result) { // 記錄進入當前節(jié)點前 sb 的長度方便退出時回退 int len sb.length(); if (len 0) { sb.append(-); } sb.append(node.val); if (node.left null node.right null) { result.add(sb.toString()); } else { if (node.left ! null) { dfs(node.left, sb, result); } if (node.right ! null) { dfs(node.right, sb, result); } } // 核心回溯恢復(fù)到進入當前節(jié)點之前的狀態(tài) sb.setLength(len); }重點看最后一行sb.setLength(len)。我在很多培訓班同學的代碼里見過這種 bug字符串拼接對了結(jié)果忘了回退最后輸出的路徑越長越長或者把左子樹的節(jié)點串到了右子樹路徑里。如果你也遇到路徑“串味”的情況十有八九是撤銷沒寫對。3.3 邊界條件空樹、單節(jié)點和“1-”的干擾這道題的邊界條件不多但每一個都很容易踩空樹返回空列表。我在代碼開頭就先判了root null。只有一個根節(jié)點路徑應(yīng)該是1而不是1-。這個“多余的 -”是新手高頻翻車點。所以拼接邏輯里我判斷了len 0才加箭頭保證根節(jié)點前沒有-。葉子節(jié)點的判斷必須嚴格為node.left null node.right null。只判斷一邊為空是不嚴謹?shù)谋热缫粋€節(jié)點只有左孩子沒有右孩子它不是葉子路徑還必須繼續(xù)走到真正的葉子。我的建議是寫完代碼后自己輸入三個測試用例[]、[1]、[1,2,3]手算一下期望輸出再跑基本能把邊界問題全部暴露出來。3.4 這會是你第一次真正理解“回溯”結(jié)構(gòu)回溯這個詞在 257 這道題里被體現(xiàn)得淋漓盡致。你在 StringBuilder 里追加節(jié)點進入子樹然后再遞歸回來把字符串縮短——這就是標準回溯模板的原型。把這段邏輯抽象一下記錄當前現(xiàn)場 做出選擇追加當前節(jié)點 遞歸進入下一層 撤銷選擇回到現(xiàn)場這個模板你會反復(fù)見到組合問題、排列問題、子集問題本質(zhì)上都是這種“做選擇-遞歸-撤銷”的循環(huán)。所以 257 看起來只是二叉樹路徑題實際上是你第一次在代碼里直觀地看見回溯。我強烈建議你在刷完這道題后把上面的抽象模板抄在筆記里后面學回溯時會感謝今天的自己。4. 404. 左葉子之和左葉子的定義比想象中更容易繞暈4.1 “左葉子”的完整定義與兩個反直覺例子“左葉子之和”聽起來很簡單把左葉子節(jié)點上的值加起來。但什么是左葉子必須先給它一個嚴謹定義這個節(jié)點是某個節(jié)點的左孩子這個節(jié)點自己沒有左右孩子。有兩點反直覺的地方要注意。第一一個節(jié)點即使是右子樹的節(jié)點只要它是父節(jié)點的左孩子同時是葉子就算左葉子。第二根節(jié)點哪怕沒有左右孩子也不算左葉子因為它沒有父節(jié)點沒有“左孩子”這個身份。舉個容易想歪的例子7 / \ 5 6 / 8這里 8 是 6 的左孩子同時 8 自己也是葉子所以 8 是左葉子它的值應(yīng)該被計入。很多人看到“左葉子”三個字下意識以為只有整棵樹的左半邊才算這就錯了?！白蟆边@個屬性只和父節(jié)點相關(guān)和它在整棵樹里的位置無關(guān)。再來一個更刁鉆的1 / \ 2 3 / \ 4 54 是 2 的左孩子、是葉子計入5 是 2 的右孩子即使它是葉子也不計數(shù)。所以這一棵樹的左葉子之和是 4。4.2 遞歸寫法用父節(jié)點視角去判定孩子既然左葉子的判定依賴于“父節(jié)點”遞歸遍歷時就別指望在訪問到某個節(jié)點的時候只靠它自己判斷而應(yīng)該在訪問父節(jié)點時檢查它的左孩子。class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } int sum 0; // 當前節(jié)點的左孩子是葉子如果是直接累加 if (root.left ! null root.left.left null root.left.right null) { sum root.left.val; } // 左子樹里可能還有左葉子繼續(xù)遞歸 sum sumOfLeftLeaves(root.left); // 右子樹里也可能有左葉子比如4.1里的8不能漏掉 sum sumOfLeftLeaves(root.right); return sum; } }注意最后兩行左子樹要遞歸右子樹也要遞歸。哪怕右孩子本身是葉子如果它下面是空的遞歸進去返回 0但如果右子樹內(nèi)部存在“父節(jié)點的左孩子是葉子”的情況這部分值必須被統(tǒng)計到。漏遞歸右子樹是這道題最常見的邏輯錯誤。還有一種更極簡的寫法把所有判斷都濃縮進一個遞歸返回public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } if (root.left ! null root.left.left null root.left.right null) { return root.left.val sumOfLeftLeaves(root.right); } return sumOfLeftLeaves(root.left) sumOfLeftLeaves(root.right); }這個版本把“左孩子是左葉子”和“遞歸找其他左葉子”合并成一行代碼更短但可讀性略差。我還是推薦第一種寫法因為面試時你需要邊寫邊講邏輯拆開更利于溝通。4.3 迭代寫法棧里彈出的每個節(jié)點都可以做一次檢查遞歸本質(zhì)上是系統(tǒng)幫你維護了一個調(diào)用棧迭代寫法無非是把它變成顯式棧。用前序、中序、后序哪種都行因為這道題只需要把所有節(jié)點拜訪一遍順序不影響累加結(jié)果。public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } DequeTreeNode stack new ArrayDeque(); stack.push(root); int sum 0; while (!stack.isEmpty()) { TreeNode node stack.pop(); // 每次彈出一個節(jié)點先檢查它的左孩子 if (node.left ! null node.left.left null node.left.right null) { sum node.left.val; } if (node.left ! null) { stack.push(node.left); } if (node.right ! null) { stack.push(node.right); } } return sum; }這里有個小優(yōu)化點左葉子節(jié)點本身不需要再壓入棧因為判斷它是不是左葉子在父節(jié)點出棧時就已經(jīng)完成了。真正需要繼續(xù)壓棧的是那些“可能含有更多左葉子”的子樹。所以你可以像我上面這樣先不管三七二十一左右孩子都壓棧簡單清晰也可以對左葉子節(jié)點額外做剪枝不把它壓棧減少一次無意義的彈出。兩者都正確寫你順手的。4.4 邊界情況對照表場景期望結(jié)果背后的原因空樹0沒有節(jié)點可加只有一個根節(jié)點0根節(jié)點沒有父節(jié)點不是任何人的左孩子根節(jié)點只有右孩子右孩子是葉子0右葉子不計數(shù)根節(jié)點的左孩子是葉子加左孩子值左孩子同時滿足“是父親的左孩子”和“是葉子”右子樹里存在父節(jié)點的左葉子需要計入“左”只取決于父節(jié)點的左側(cè)關(guān)系寫代碼前先把這個表在心里過一遍基本可以寫一次就 AC。5. 222. 完全二叉樹的節(jié)點個數(shù)從O(n)到O(log^2 n)的特性紅利5.1 最樸素的解法任何二叉樹都能數(shù)先別管“完全二叉樹”這幾個字把題目當成“給我任意一顆二叉樹統(tǒng)計節(jié)點數(shù)”。這幾乎是遞歸最入門級的題目public int countNodes(TreeNode root) { if (root null) { return 0; } return 1 countNodes(root.left) countNodes(root.right); }這行邏輯不需要動腦子當前節(jié)點算一個加上左子樹的節(jié)點數(shù)再加上右子樹的節(jié)點數(shù)。用層序遍歷BFS也能做維護一個隊列每彈出一個節(jié)點計數(shù)加 1然后把左右孩子入隊。兩種解法都是 O(n) 的時間復(fù)雜度。面試時先回答這個版本是穩(wěn)妥的它證明你有基礎(chǔ)能力。但面試官如果追問“這棵樹除了是二叉樹還是完全二叉樹你能利用這個條件嗎”就到了今天題單的關(guān)鍵部分。5.2 滿二叉樹公式帶來的優(yōu)化思路完全二叉樹有一個很強的性質(zhì)除了最后一層其他層都是滿的而且最后一層的節(jié)點都盡可能靠左排列。這意味著對完全二叉樹里的任何一個子樹它有可能是滿二叉樹也有可能不是。怎么快速判斷某棵子樹是不是滿二叉樹看兩個深度從它的左孩子出發(fā)一路朝左下走能走幾步從它的右孩子出發(fā)一路朝右下走能走幾步。如果兩邊步數(shù)相等說明左子樹和右子樹的最外邊界高度一樣——它是一棵滿二叉樹。滿二叉樹的節(jié)點數(shù)有現(xiàn)成公式2^h - 1其中 h 是層數(shù)。一步不用遞歸直接套公式。如果兩邊步數(shù)不相等說明這棵子樹沒滿那就只能用老辦法節(jié)點數(shù) 1 左子樹節(jié)點數(shù) 右子樹節(jié)點數(shù)遞歸往下分解。由于完全二叉樹的特殊結(jié)構(gòu)遞歸每一層都會砍掉一半“不確定區(qū)域”總體效率遠高于 O(n)。5.3 遞歸實現(xiàn)與容易寫錯的一行位運算優(yōu)化版代碼如下public int countNodes(TreeNode root) { if (root null) { return 0; } int leftDepth 0; int rightDepth 0; TreeNode left root.left; TreeNode right root.right; while (left ! null) { leftDepth; left left.left; } while (right ! null) { rightDepth; right right.right; } // 如果左外邊界和右外邊界深度相等說明這棵子樹是滿二叉樹 if (leftDepth rightDepth) { // 滿二叉樹節(jié)點數(shù) 2^(leftDepth1) - 1 return (2 leftDepth) - 1; } // 不是滿二叉樹遞歸去左右子樹里繼續(xù)判斷 return 1 countNodes(root.left) countNodes(root.right); }這行位運算是整個代碼里最容易被寫錯的一行。我見過很多人寫成(1 leftDepth) - 1算出來的結(jié)果總是少節(jié)點。原因在于我的leftDepth是“沿最左側(cè)走的時候經(jīng)過的邊的數(shù)量”不是“層數(shù)”。比如只有根節(jié)點的樹走 0 條邊leftDepth 0但滿二叉樹節(jié)點數(shù)是 1也就是2^(01) - 1 1。用位運算表達就是(2 0) - 1 1。如果寫成(1 0) - 1 0根節(jié)點都被你數(shù)丟了。如果你對位運算不熟用Math.pow(2, leftDepth 1) - 1效果完全一樣只是稍慢。我不建議為了炫技而用位運算前提是你真明白2 x的含義。5.4 復(fù)雜度對比與二分思路的一句話說明普通遞歸復(fù)雜度 O(n)優(yōu)化版復(fù)雜度 O(log^2 n)。怎么估算的每調(diào)用一次遞歸就會在兩個 while 循環(huán)里沿邊界往下走這一步是 O(log n)而遞歸的深度最多也是 O(log n)——因為完全二叉樹的樹高是對數(shù)級的。兩個 O(log n) 相乘就是 O(log^2 n)。舉一個直觀的數(shù)字假設(shè)樹里有 10 億個節(jié)點普通遞歸要真的訪問 10 億個節(jié)點優(yōu)化版大約只需要幾千次操作。這個差距在極端測試數(shù)據(jù)下是肉眼可見的。力扣官方還有一種更進階的解法先確定樹的高度再二分最后一層的節(jié)點數(shù)量用位掩碼驗證某個編號對應(yīng)的節(jié)點是否存在。思路很漂亮但訓練營階段能把“滿二叉樹直接套公式”這個優(yōu)化想明白已經(jīng)超過了大多數(shù)刷題者。我這里不展開先把基礎(chǔ)優(yōu)化吃透。6. 四道題刷完我總結(jié)的二叉樹遞歸檢查清單6.1 遞歸三部曲在這四道題上的映射如果要把今天四道題濃縮成一張思維地圖那它們就是在反復(fù)回答三個問題。第一這個函數(shù)該返回什么。110 返回子樹高度并用 -1 表達“不平衡”257 不需要返回具體值只需要把路徑寫進結(jié)果集404 返回左葉子之和222 返回節(jié)點個數(shù)。返回值定了遞歸的骨架就定了。第二什么時候停下來。樹的遞歸幾乎無一例外第一反應(yīng)永遠是“空節(jié)點怎么處理”。110 里空節(jié)點返回 0257 里空節(jié)點直接 return404 里空節(jié)點返回 0222 里空節(jié)點返回 0。然后再考慮真正的“終結(jié)條件”比如 257 的葉子節(jié)點要把路徑收集進結(jié)果集。第三單層邏輯做什么。這個最靈活110 在單層比較高度差257 在單層拼接路徑404 在單層判斷左孩子是否為葉子222 在單層判斷是否為滿二叉樹。單層邏輯寫對了遞歸基本成功了一大半。6.2 一張表記住四道題的易錯點題目核心遍歷方式返回值/狀態(tài)最高頻易錯點110 平衡二叉樹后序遍歷int 高度-1 表示失衡混淆高度深度忘了剪枝257 二叉樹的所有路徑前序遍歷無返回值收集結(jié)果StringBuilder 忘記回溯多出“-”404 左葉子之和任意遍歷整型累加和漏遞歸右子樹根節(jié)點誤判為左葉子222 完全二叉樹節(jié)點個數(shù)后序 特性判斷int 節(jié)點數(shù)滿二叉樹公式里的 1 寫錯位運算搞混這張表我建議抄在解題筆記里刷題中期拿出來復(fù)習一遍比再刷十道新題更有用。尤其是 257 的“回溯”和 222 的“滿二叉樹公式”是訓練營同學互相提問時最容易翻車的地方。6.3 最后一件事把“為什么”講清楚第十五天刷完我最大的體會是二叉樹的遞歸題從來不靠背題而是靠把“遍歷順序、返回值、邊界條件”這三個問題想清楚。四道題看起來各自獨立其實是同一套思維在四個場景下的反復(fù)演練。所以如果今天你也剛好刷到這里別急著去做下一批題目。先把每道題的代碼遮住口頭給自己講一遍“110 為什么用后序257 為什么用前序404 為什么可以隨便用任何順序222 的滿二叉樹公式為什么是 2 的 h 次方減 1”這幾個問題能流利答出來今天的四道題才算真正消化了。后面遇到的二叉樹遞歸題大概率都是這些套路的變形而已。 二叉樹遞歸四題精講：平衡判斷、路徑回溯、左葉子與完全二叉樹優(yōu)化
第十五天的題單一拉出來我第一反應(yīng)是“這四道題都不難”?？烧鎰邮炙⑼瓴虐l(fā)現(xiàn)它們湊在一起是有講究的110、257、404、222幾乎把二叉樹遞歸里最核心的幾件事——后序求高度、前序收集路徑、用父節(jié)點視角判斷特殊節(jié)點、利用完全二叉樹特性優(yōu)化——各出了一道代表題。如果你也在跟代碼隨想錄算法訓練營刷二叉樹這一天值得停下來多琢磨一會兒別急著追求AC數(shù)量把這四道題的“為什么”吃透后面寫回溯和遞歸會順手很多。1. 第十五天的四道題正好湊齊二叉樹遞歸的三種套路1.1 一天的題單難度梯度其實很講究先說結(jié)論這四道題按難度排大概是 404 257 ≈ 110 222。但難度并非唯一線索更重要的是它們在遞歸思路上剛好互補。110平衡二叉樹要求你從子樹返回高度本質(zhì)是后序遍歷左-右-中因為必須先知道左右子樹的高度才能判斷當前節(jié)點是否平衡。257二叉樹的所有路徑要求從根走到葉子邊收集邊記錄本質(zhì)是前序遍歷中-左-右因為路徑的順序天然是從根開始的。404左葉子之和看起來簡單但真正的坎在于“左葉子”這個定義本身——它必須靠父節(jié)點來判定這是很多新手繞不過去的彎。222完全二叉樹的節(jié)點個數(shù)如果只求暴力解一兩分鐘就能寫出來可一旦想到“完全二叉樹”四個字你就應(yīng)該停下來想一想能不能利用滿二叉樹的數(shù)學性質(zhì)把復(fù)雜度從 O(n) 降到 O(log^2 n)。所以這一天的題單相當于把二叉樹遞歸里的三種“手感”都練了一遍求值用后序、收集路徑用前序、特性利用靠觀察和數(shù)學推導。這四道題我強烈建議不要只看題解自己先寫一版再對照優(yōu)化版收獲會翻倍。1.2 適合誰來讀讀之前需要什么基礎(chǔ)這篇復(fù)盤適合正在刷二叉樹、但還處在“每次遞歸都要重新想一遍”階段的讀者。如果你能區(qū)分先序/中序/后序的區(qū)別、能寫出遞歸版前序遍歷那么接下來的內(nèi)容你完全吃得下。如果你連遞歸都還有些發(fā)怵也沒關(guān)系我會先把每道題的遞歸三步曲拆開講清楚。刷二叉樹題目我一直堅持一個理念不要背題要背“套路”。樹這類結(jié)構(gòu)天生適合遞歸因為樹的子樹還是樹。而遞歸的難點從來不在“怎么寫”而在“這個函數(shù)該返回什么、什么時候停下來、單層邏輯做什么”。這四道題恰好就是把這三個問題分別放大給你看。2. 110. 平衡二叉樹先分清高度和深度后序遞歸才不會亂2.1 題目在考什么一顆樹到底怎么算“平衡”力扣 110 的平衡二叉樹定義每個節(jié)點的左右子樹高度差絕對值不超過 1。網(wǎng)上很多題解寫得很隨意但這里有個概念陷阱就是“高度”和“深度”經(jīng)常被混著用。我自己的記憶方法是深度是往下的從根到你所在節(jié)點高度是往上的從你所在節(jié)點到葉子。所以根節(jié)點的深度最大葉子節(jié)點的深度最小反過來葉子節(jié)點的高度最小約定為 1根節(jié)點的高度是整棵樹的最大深度。判斷一顆樹是否平衡邏輯上需要先知道左右子樹各自有多高再比較差值。這意味著在遞歸返回時你必須要得到“這棵子樹到底有多高”這個數(shù)字。如果某個子樹已經(jīng)不平衡了還需要繼續(xù)算它的高度嗎不需要直接向上傳遞一個“失敗信號”讓整棵樹提前結(jié)束。這個題目最容易犯的錯誤是想著“在每個節(jié)點用前序遍歷求它的深度再比較左右孩子深度的差”。這個思路看著對但實際上你求出來的“深度”并不是該節(jié)點子樹的高度而且每到一個節(jié)點都重新向下數(shù)一遍深度會帶來大量重復(fù)計算。正確姿勢只有一個用后序遍歷求高度。2.2 遞歸三部曲落地用-1既當高度又當失衡標記遞歸不管多繞先想三件事參數(shù)和返回值是什么、終止條件是什么、單層邏輯做什么。這道題我要返回高度但還要額外表達“這顆子樹已經(jīng)不平衡了”。兩個信息合并我的返回值就用一個 int正常情況返回高度一旦發(fā)現(xiàn)不平衡就返回 -1。這樣上層節(jié)點拿到 -1 后立刻就能判斷出整棵樹已經(jīng)不平衡沒必要再往下朝右子樹遞歸了。class Solution { public boolean isBalanced(TreeNode root) { return getHeight(root) ! -1; } private int getHeight(TreeNode node) { if (node null) { return 0; // 空節(jié)點高度為0 } int leftHeight getHeight(node.left); if (leftHeight -1) { return -1; // 左子樹已經(jīng)不平衡 } int rightHeight getHeight(node.right); if (rightHeight -1) { return -1; // 右子樹已經(jīng)不平衡 } // 當前節(jié)點的平衡性左右高度差不能超過1 if (Math.abs(leftHeight - rightHeight) 1) { return -1; } // 返回當前節(jié)點作為根的子樹的真實高度 return Math.max(leftHeight, rightHeight) 1; } }這段代碼建議親手抄一遍再默寫一遍。注意最后一行是Math.max(left, right) 1不是Math.min。這個 1 代表把當前節(jié)點自己也算進高度里這是整段遞歸字數(shù)最少卻最容易出錯的地方。2.3 提前返回的剪枝效果別把明明不平衡的子樹繼續(xù)算下去遞歸版里連續(xù)兩個if (leftHeight -1) return -1;看起來多此一舉實際是剪枝的精髓。我刷題時一開始偷懶省略了這兩個判斷心想反正最后Math.abs也會發(fā)現(xiàn)不平衡。但仔細一想如果左子樹已經(jīng)返回 -1說明左子樹內(nèi)部已經(jīng)失衡這時候繼續(xù)算右子樹的高度沒有任何意義純屬浪費時間。極端一點的情況是這樣一顆樹根節(jié)點的左子樹嚴重失衡而右子樹是節(jié)點數(shù)量極大的完全二叉樹。如果不剪枝左子樹發(fā)現(xiàn)失衡后代碼還要去把右子樹完整遍歷一遍白白花費 O(n) 時間剪枝后左子樹返回 -1 的那一剎那整個遞歸就一路向上退出右子樹根本不會被訪問到。這種“短路求值”思想在后面的回溯剪枝、動態(tài)規(guī)劃優(yōu)化里會反復(fù)出現(xiàn)越早習慣越省力。2.4 迭代思路能懂更好不懂也不影響做題遞歸版已經(jīng)足夠應(yīng)付面試和筆試但面試官偶爾會追問一句“你能用迭代寫嗎”。迭代思路其實是用顯式棧模擬后序遍歷同時用一個哈希表記錄每個節(jié)點的高度?；咎茁肥莾蓪拥谝粚佑脳ＤM“左-右-中”的后序訪問順序。遍歷到中間節(jié)點時先不斷把左孩子、右孩子壓棧確保左右子樹都處理完了才輪到中間節(jié)點。第二層每個中間節(jié)點出棧時從哈希表里查詢左右子樹的高度比較差值然后把當前節(jié)點的高度Math.max(left, right) 1存進哈希表。我在這里不放完整迭代代碼因為后序迭代本身比較繞很容易把初學者整懵。如果你目前還在建立遞歸直覺優(yōu)先吃透遞歸版等遞歸版熟練了再看迭代作為思維擴展。面試中能寫出簡潔遞歸并解釋清楚剪枝邏輯已經(jīng)能拿不錯的分數(shù)。3. 257. 二叉樹的所有路徑前序遍歷收集路徑遞歸返回時記得撤銷3.1 為什么一定要前序遍歷257 題要求返回所有從根到葉子的路徑比如[1-2-5, 1-3]。路徑的起點永遠是根順序永遠是“根在左、葉子在右”所以遍歷順序天然就是先訪問根再訪問左孩子再訪問右孩子也就是前序遍歷。中序和后序遍歷都會把根節(jié)點留在中間或最后處理你想按“從根到葉子”的順序拼接路徑還得額外處理字符串順序非常別扭。這也是一個判斷經(jīng)驗看到“從根到葉子”這種強依賴順序的需求優(yōu)先想前序遍歷。3.2 兩種實現(xiàn)String的天然回溯 與 StringBuilder的顯式回溯這道題最直觀的寫法是遞歸時傳一個 String因為 Java 的 String 是不可變的每次拼接都會生成新對象天然幫你“隔離”了路徑污染。class Solution { public ListString binaryTreePaths(TreeNode root) { ListString result new ArrayList(); if (root null) { return result; } dfs(root, , result); return result; } private void dfs(TreeNode node, String path, ListString result) { // 到達葉子生成一條完整路徑 if (node.left null node.right null) { result.add(path node.val); return; } String nextPath path node.val -; if (node.left ! null) { dfs(node.left, nextPath, result); } if (node.right ! null) { dfs(node.right, nextPath, result); } } }這種寫法的優(yōu)點是思路清晰新手也好懂缺點是每層遞歸都會新建字符串在節(jié)點數(shù)量很大的場景下會有一定開銷。但算法訓練階段先跑通邏輯比摳性能重要。用可變對象就得小心了。拿 StringBuilder 舉例由于它是可變的遞歸返回后如果不手動“撤銷”剛才追加的內(nèi)容左子樹殘留的路徑片段會污染右子樹的拼接結(jié)果。private void dfs(TreeNode node, StringBuilder sb, ListString result) { // 記錄進入當前節(jié)點前 sb 的長度方便退出時回退 int len sb.length(); if (len 0) { sb.append(-); } sb.append(node.val); if (node.left null node.right null) { result.add(sb.toString()); } else { if (node.left ! null) { dfs(node.left, sb, result); } if (node.right ! null) { dfs(node.right, sb, result); } } // 核心回溯恢復(fù)到進入當前節(jié)點之前的狀態(tài) sb.setLength(len); }重點看最后一行sb.setLength(len)。我在很多培訓班同學的代碼里見過這種 bug字符串拼接對了結(jié)果忘了回退最后輸出的路徑越長越長或者把左子樹的節(jié)點串到了右子樹路徑里。如果你也遇到路徑“串味”的情況十有八九是撤銷沒寫對。3.3 邊界條件空樹、單節(jié)點和“1-”的干擾這道題的邊界條件不多但每一個都很容易踩空樹返回空列表。我在代碼開頭就先判了root null。只有一個根節(jié)點路徑應(yīng)該是1而不是1-。這個“多余的 -”是新手高頻翻車點。所以拼接邏輯里我判斷了len 0才加箭頭保證根節(jié)點前沒有-。葉子節(jié)點的判斷必須嚴格為node.left null node.right null。只判斷一邊為空是不嚴謹?shù)谋热缫粋€節(jié)點只有左孩子沒有右孩子它不是葉子路徑還必須繼續(xù)走到真正的葉子。我的建議是寫完代碼后自己輸入三個測試用例[]、[1]、[1,2,3]手算一下期望輸出再跑基本能把邊界問題全部暴露出來。3.4 這會是你第一次真正理解“回溯”結(jié)構(gòu)回溯這個詞在 257 這道題里被體現(xiàn)得淋漓盡致。你在 StringBuilder 里追加節(jié)點進入子樹然后再遞歸回來把字符串縮短——這就是標準回溯模板的原型。把這段邏輯抽象一下記錄當前現(xiàn)場 做出選擇追加當前節(jié)點 遞歸進入下一層 撤銷選擇回到現(xiàn)場這個模板你會反復(fù)見到組合問題、排列問題、子集問題本質(zhì)上都是這種“做選擇-遞歸-撤銷”的循環(huán)。所以 257 看起來只是二叉樹路徑題實際上是你第一次在代碼里直觀地看見回溯。我強烈建議你在刷完這道題后把上面的抽象模板抄在筆記里后面學回溯時會感謝今天的自己。4. 404. 左葉子之和左葉子的定義比想象中更容易繞暈4.1 “左葉子”的完整定義與兩個反直覺例子“左葉子之和”聽起來很簡單把左葉子節(jié)點上的值加起來。但什么是左葉子必須先給它一個嚴謹定義這個節(jié)點是某個節(jié)點的左孩子這個節(jié)點自己沒有左右孩子。有兩點反直覺的地方要注意。第一一個節(jié)點即使是右子樹的節(jié)點只要它是父節(jié)點的左孩子同時是葉子就算左葉子。第二根節(jié)點哪怕沒有左右孩子也不算左葉子因為它沒有父節(jié)點沒有“左孩子”這個身份。舉個容易想歪的例子7 / \ 5 6 / 8這里 8 是 6 的左孩子同時 8 自己也是葉子所以 8 是左葉子它的值應(yīng)該被計入。很多人看到“左葉子”三個字下意識以為只有整棵樹的左半邊才算這就錯了?！白蟆边@個屬性只和父節(jié)點相關(guān)和它在整棵樹里的位置無關(guān)。再來一個更刁鉆的1 / \ 2 3 / \ 4 54 是 2 的左孩子、是葉子計入5 是 2 的右孩子即使它是葉子也不計數(shù)。所以這一棵樹的左葉子之和是 4。4.2 遞歸寫法用父節(jié)點視角去判定孩子既然左葉子的判定依賴于“父節(jié)點”遞歸遍歷時就別指望在訪問到某個節(jié)點的時候只靠它自己判斷而應(yīng)該在訪問父節(jié)點時檢查它的左孩子。class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } int sum 0; // 當前節(jié)點的左孩子是葉子如果是直接累加 if (root.left ! null root.left.left null root.left.right null) { sum root.left.val; } // 左子樹里可能還有左葉子繼續(xù)遞歸 sum sumOfLeftLeaves(root.left); // 右子樹里也可能有左葉子比如4.1里的8不能漏掉 sum sumOfLeftLeaves(root.right); return sum; } }注意最后兩行左子樹要遞歸右子樹也要遞歸。哪怕右孩子本身是葉子如果它下面是空的遞歸進去返回 0但如果右子樹內(nèi)部存在“父節(jié)點的左孩子是葉子”的情況這部分值必須被統(tǒng)計到。漏遞歸右子樹是這道題最常見的邏輯錯誤。還有一種更極簡的寫法把所有判斷都濃縮進一個遞歸返回public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } if (root.left ! null root.left.left null root.left.right null) { return root.left.val sumOfLeftLeaves(root.right); } return sumOfLeftLeaves(root.left) sumOfLeftLeaves(root.right); }這個版本把“左孩子是左葉子”和“遞歸找其他左葉子”合并成一行代碼更短但可讀性略差。我還是推薦第一種寫法因為面試時你需要邊寫邊講邏輯拆開更利于溝通。4.3 迭代寫法棧里彈出的每個節(jié)點都可以做一次檢查遞歸本質(zhì)上是系統(tǒng)幫你維護了一個調(diào)用棧迭代寫法無非是把它變成顯式棧。用前序、中序、后序哪種都行因為這道題只需要把所有節(jié)點拜訪一遍順序不影響累加結(jié)果。public int sumOfLeftLeaves(TreeNode root) { if (root null) { return 0; } DequeTreeNode stack new ArrayDeque(); stack.push(root); int sum 0; while (!stack.isEmpty()) { TreeNode node stack.pop(); // 每次彈出一個節(jié)點先檢查它的左孩子 if (node.left ! null node.left.left null node.left.right null) { sum node.left.val; } if (node.left ! null) { stack.push(node.left); } if (node.right ! null) { stack.push(node.right); } } return sum; }這里有個小優(yōu)化點左葉子節(jié)點本身不需要再壓入棧因為判斷它是不是左葉子在父節(jié)點出棧時就已經(jīng)完成了。真正需要繼續(xù)壓棧的是那些“可能含有更多左葉子”的子樹。所以你可以像我上面這樣先不管三七二十一左右孩子都壓棧簡單清晰也可以對左葉子節(jié)點額外做剪枝不把它壓棧減少一次無意義的彈出。兩者都正確寫你順手的。4.4 邊界情況對照表場景期望結(jié)果背后的原因空樹0沒有節(jié)點可加只有一個根節(jié)點0根節(jié)點沒有父節(jié)點不是任何人的左孩子根節(jié)點只有右孩子右孩子是葉子0右葉子不計數(shù)根節(jié)點的左孩子是葉子加左孩子值左孩子同時滿足“是父親的左孩子”和“是葉子”右子樹里存在父節(jié)點的左葉子需要計入“左”只取決于父節(jié)點的左側(cè)關(guān)系寫代碼前先把這個表在心里過一遍基本可以寫一次就 AC。5. 222. 完全二叉樹的節(jié)點個數(shù)從O(n)到O(log^2 n)的特性紅利5.1 最樸素的解法任何二叉樹都能數(shù)先別管“完全二叉樹”這幾個字把題目當成“給我任意一顆二叉樹統(tǒng)計節(jié)點數(shù)”。這幾乎是遞歸最入門級的題目public int countNodes(TreeNode root) { if (root null) { return 0; } return 1 countNodes(root.left) countNodes(root.right); }這行邏輯不需要動腦子當前節(jié)點算一個加上左子樹的節(jié)點數(shù)再加上右子樹的節(jié)點數(shù)。用層序遍歷BFS也能做維護一個隊列每彈出一個節(jié)點計數(shù)加 1然后把左右孩子入隊。兩種解法都是 O(n) 的時間復(fù)雜度。面試時先回答這個版本是穩(wěn)妥的它證明你有基礎(chǔ)能力。但面試官如果追問“這棵樹除了是二叉樹還是完全二叉樹你能利用這個條件嗎”就到了今天題單的關(guān)鍵部分。5.2 滿二叉樹公式帶來的優(yōu)化思路完全二叉樹有一個很強的性質(zhì)除了最后一層其他層都是滿的而且最后一層的節(jié)點都盡可能靠左排列。這意味著對完全二叉樹里的任何一個子樹它有可能是滿二叉樹也有可能不是。怎么快速判斷某棵子樹是不是滿二叉樹看兩個深度從它的左孩子出發(fā)一路朝左下走能走幾步從它的右孩子出發(fā)一路朝右下走能走幾步。如果兩邊步數(shù)相等說明左子樹和右子樹的最外邊界高度一樣——它是一棵滿二叉樹。滿二叉樹的節(jié)點數(shù)有現(xiàn)成公式2^h - 1其中 h 是層數(shù)。一步不用遞歸直接套公式。如果兩邊步數(shù)不相等說明這棵子樹沒滿那就只能用老辦法節(jié)點數(shù) 1 左子樹節(jié)點數(shù) 右子樹節(jié)點數(shù)遞歸往下分解。由于完全二叉樹的特殊結(jié)構(gòu)遞歸每一層都會砍掉一半“不確定區(qū)域”總體效率遠高于 O(n)。5.3 遞歸實現(xiàn)與容易寫錯的一行位運算優(yōu)化版代碼如下public int countNodes(TreeNode root) { if (root null) { return 0; } int leftDepth 0; int rightDepth 0; TreeNode left root.left; TreeNode right root.right; while (left ! null) { leftDepth; left left.left; } while (right ! null) { rightDepth; right right.right; } // 如果左外邊界和右外邊界深度相等說明這棵子樹是滿二叉樹 if (leftDepth rightDepth) { // 滿二叉樹節(jié)點數(shù) 2^(leftDepth1) - 1 return (2 leftDepth) - 1; } // 不是滿二叉樹遞歸去左右子樹里繼續(xù)判斷 return 1 countNodes(root.left) countNodes(root.right); }這行位運算是整個代碼里最容易被寫錯的一行。我見過很多人寫成(1 leftDepth) - 1算出來的結(jié)果總是少節(jié)點。原因在于我的leftDepth是“沿最左側(cè)走的時候經(jīng)過的邊的數(shù)量”不是“層數(shù)”。比如只有根節(jié)點的樹走 0 條邊leftDepth 0但滿二叉樹節(jié)點數(shù)是 1也就是2^(01) - 1 1。用位運算表達就是(2 0) - 1 1。如果寫成(1 0) - 1 0根節(jié)點都被你數(shù)丟了。如果你對位運算不熟用Math.pow(2, leftDepth 1) - 1效果完全一樣只是稍慢。我不建議為了炫技而用位運算前提是你真明白2 x的含義。5.4 復(fù)雜度對比與二分思路的一句話說明普通遞歸復(fù)雜度 O(n)優(yōu)化版復(fù)雜度 O(log^2 n)。怎么估算的每調(diào)用一次遞歸就會在兩個 while 循環(huán)里沿邊界往下走這一步是 O(log n)而遞歸的深度最多也是 O(log n)——因為完全二叉樹的樹高是對數(shù)級的。兩個 O(log n) 相乘就是 O(log^2 n)。舉一個直觀的數(shù)字假設(shè)樹里有 10 億個節(jié)點普通遞歸要真的訪問 10 億個節(jié)點優(yōu)化版大約只需要幾千次操作。這個差距在極端測試數(shù)據(jù)下是肉眼可見的。力扣官方還有一種更進階的解法先確定樹的高度再二分最后一層的節(jié)點數(shù)量用位掩碼驗證某個編號對應(yīng)的節(jié)點是否存在。思路很漂亮但訓練營階段能把“滿二叉樹直接套公式”這個優(yōu)化想明白已經(jīng)超過了大多數(shù)刷題者。我這里不展開先把基礎(chǔ)優(yōu)化吃透。6. 四道題刷完我總結(jié)的二叉樹遞歸檢查清單6.1 遞歸三部曲在這四道題上的映射如果要把今天四道題濃縮成一張思維地圖那它們就是在反復(fù)回答三個問題。第一這個函數(shù)該返回什么。110 返回子樹高度并用 -1 表達“不平衡”257 不需要返回具體值只需要把路徑寫進結(jié)果集404 返回左葉子之和222 返回節(jié)點個數(shù)。返回值定了遞歸的骨架就定了。第二什么時候停下來。樹的遞歸幾乎無一例外第一反應(yīng)永遠是“空節(jié)點怎么處理”。110 里空節(jié)點返回 0257 里空節(jié)點直接 return404 里空節(jié)點返回 0222 里空節(jié)點返回 0。然后再考慮真正的“終結(jié)條件”比如 257 的葉子節(jié)點要把路徑收集進結(jié)果集。第三單層邏輯做什么。這個最靈活110 在單層比較高度差257 在單層拼接路徑404 在單層判斷左孩子是否為葉子222 在單層判斷是否為滿二叉樹。單層邏輯寫對了遞歸基本成功了一大半。6.2 一張表記住四道題的易錯點題目核心遍歷方式返回值/狀態(tài)最高頻易錯點110 平衡二叉樹后序遍歷int 高度-1 表示失衡混淆高度深度忘了剪枝257 二叉樹的所有路徑前序遍歷無返回值收集結(jié)果StringBuilder 忘記回溯多出“-”404 左葉子之和任意遍歷整型累加和漏遞歸右子樹根節(jié)點誤判為左葉子222 完全二叉樹節(jié)點個數(shù)后序 特性判斷int 節(jié)點數(shù)滿二叉樹公式里的 1 寫錯位運算搞混這張表我建議抄在解題筆記里刷題中期拿出來復(fù)習一遍比再刷十道新題更有用。尤其是 257 的“回溯”和 222 的“滿二叉樹公式”是訓練營同學互相提問時最容易翻車的地方。6.3 最后一件事把“為什么”講清楚第十五天刷完我最大的體會是二叉樹的遞歸題從來不靠背題而是靠把“遍歷順序、返回值、邊界條件”這三個問題想清楚。四道題看起來各自獨立其實是同一套思維在四個場景下的反復(fù)演練。所以如果今天你也剛好刷到這里別急著去做下一批題目。先把每道題的代碼遮住口頭給自己講一遍“110 為什么用后序257 為什么用前序404 為什么可以隨便用任何順序222 的滿二叉樹公式為什么是 2 的 h 次方減 1”這幾個問題能流利答出來今天的四道題才算真正消化了。后面遇到的二叉樹遞歸題大概率都是這些套路的變形而已。