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