1. 先說(shuō)清楚這道題到底在考什么hot100 的 199. 二叉樹(shù)的右視圖我刷第一遍的時(shí)候其實(shí)沒(méi)太當(dāng)回事覺(jué)得無(wú)非就是層序遍歷每層取最后一個(gè)節(jié)點(diǎn)。后來(lái)面試被追問(wèn)了幾次才發(fā)現(xiàn)這道題里藏著的點(diǎn)比想象中多。它不光是考層序還會(huì)延伸到 DFS 的變體寫(xiě)法、邊界條件的處理、以及對(duì)二叉樹(shù)遍歷本質(zhì)的理解。你要是能把這道題吃透hot100 里后面那些帶“層序”“深度”“視圖”字眼的題基本都能順手解決。題目本身不復(fù)雜給定一棵二叉樹(shù)想象自己站在它的右側(cè)按照從頂部到底部的順序返回從右側(cè)能看到的所有節(jié)點(diǎn)值。所謂“右視圖”說(shuō)白了就是每一層最右邊的那個(gè)節(jié)點(diǎn)。層序遍歷是個(gè)直觀思路深度優(yōu)先搜索其實(shí)也能寫(xiě)而且寫(xiě)法更簡(jiǎn)潔。一個(gè)小例子1 / \ 2 3 \ \ 5 4從右側(cè)看第一層看到 1第二層看到 3第三層看到 4所以結(jié)果是 [1, 3, 4]。注意第二層的節(jié)點(diǎn) 2 被 3 擋住了第三層的節(jié)點(diǎn) 5 被 4 擋住了所以不會(huì)出現(xiàn)在結(jié)果里。這道題適合誰(shuí)來(lái)刷呢我覺(jué)得是兩種人一種是剛開(kāi)始刷 hot100、想要系統(tǒng)掌握二叉樹(shù)遍歷的人另一種是已經(jīng)會(huì)層序遍歷、但想在 DFS 思路上補(bǔ)短板的人。它不是最難的題但作為二叉樹(shù)的“視圖類(lèi)”入門(mén)題性價(jià)比非常高。先說(shuō)結(jié)論右視圖的實(shí)質(zhì)就是“在每一層中優(yōu)先選擇最右側(cè)節(jié)點(diǎn)”。理解了這句話下面所有寫(xiě)法都順了。2. 層序遍歷最直覺(jué)的解法也是面試官最?lèi)?ài)讓你手寫(xiě)的第一版2.1 層序思路怎么“看到”每一層最右邊的節(jié)點(diǎn)層序遍歷用的是隊(duì)列標(biāo)準(zhǔn) BFS 流程。核心點(diǎn)在于每次進(jìn)入下一層之前先記錄當(dāng)前隊(duì)列的長(zhǎng)度 size然后只循環(huán) size 次把這層的節(jié)點(diǎn)全部彈出。彈出的過(guò)程中最后一個(gè)彈出的節(jié)點(diǎn)就是這一層的最右側(cè)節(jié)點(diǎn)。這個(gè)思路看起來(lái)簡(jiǎn)單但有一個(gè)細(xì)節(jié)是新手很容易踩坑的循環(huán)里千萬(wàn)不要直接寫(xiě)queue.size()作為循環(huán)上限因?yàn)檫@個(gè)值是會(huì)變的。你每彈出一個(gè)節(jié)點(diǎn)又會(huì)往隊(duì)列尾部壓入它的左右孩子size 會(huì)不斷增大最終導(dǎo)致一次循環(huán)把整棵樹(shù)都遍歷完層與層之間就完全分不清了。正確做法是先把當(dāng)前隊(duì)列長(zhǎng)度存到一個(gè)變量里循環(huán)固定這個(gè)長(zhǎng)度。這就是“按層處理”和“按節(jié)點(diǎn)處理”的區(qū)別。BFS 的隊(duì)列天然是先進(jìn)先出但如果你不鎖定每層的入口長(zhǎng)度隊(duì)列里的元素會(huì)跨層混在一起層序就變成了普通的廣搜失去了“層”的概念。2.2 BFS 代碼逐行拆解C 版class Solution { public: vectorint rightSideView(TreeNode* root) { vectorint ans; if (!root) return ans; // 空樹(shù)直接返回別猶豫 queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); // 關(guān)鍵鎖定當(dāng)前層的節(jié)點(diǎn)個(gè)數(shù) for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); if (i size - 1) { // 最后一個(gè)節(jié)點(diǎn)就是右視圖的節(jié)點(diǎn) ans.push_back(node-val); } if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } return ans; } };這里面幾個(gè)細(xì)節(jié)值得說(shuō)if (!root) return ans;這行寫(xiě)在最前面不是湊代碼量。二叉樹(shù)的遍歷題里空指針判斷是第一優(yōu)先級(jí)。面試時(shí)如果你忘了判空后面的node-left直接就是一個(gè)空指針訪問(wèn)運(yùn)行時(shí)直接崩潰。q.size()記錄下來(lái)之后Node* node q.front(); q.pop();的順序一定不能反也一定不能漏。彈出之后節(jié)點(diǎn)指針就失效了你要是轉(zhuǎn)過(guò)頭再去訪問(wèn)front()就是未定義行為。判斷i size - 1這個(gè)位置寫(xiě)在哪里決定了你存的是哪一層。如果你把a(bǔ)ns.push_back(node-val)放在循環(huán)體最前面那你存的就是最左邊的節(jié)點(diǎn)也就是左視圖。所以這兩個(gè)視圖之間其實(shí)就是一行代碼的區(qū)別。Python 版本也順手貼一下思路完全一樣只是語(yǔ)法上有點(diǎn)差異from collections import deque class Solution: def rightSideView(self, root: TreeNode) - List[int]: ans [] if not root: return ans q deque([root]) while q: size len(q) for i in range(size): node q.popleft() if i size - 1: ans.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return ans注意Python 里len(q)放在for i in range(size)之前和 C 的int size q.size()同理一旦進(jìn)入循環(huán)后隊(duì)列長(zhǎng)度變了你還在按原來(lái)的 size 遍歷就會(huì)漏層或者跨層。這一點(diǎn)兩種語(yǔ)言都是一個(gè)坑。2.3 為什么“每層最后一個(gè)”恰好就是最右側(cè)的節(jié)點(diǎn)有人可能會(huì)問(wèn)BFS 是按從左到右的順序遍歷一層的那最右邊的節(jié)點(diǎn)當(dāng)然就是最后一個(gè)彈出的節(jié)點(diǎn)。這沒(méi)問(wèn)題。但更深一層的原因是層序遍歷天然保證了我們?cè)诿總€(gè)層級(jí)上從左到右訪問(wèn)所有節(jié)點(diǎn)而這個(gè)“左到右”的順序是由入隊(duì)時(shí)先 left 后 right 決定的。所以如果你想改成“左視圖”有兩個(gè)方案一是入隊(duì)時(shí)先 right 后 left然后仍然取每層最后一個(gè)二是入隊(duì)順序不變但取每層第一個(gè)。兩種方式都可以但最容易記的還是改取法而不是改順序因?yàn)楦捻樞驎?huì)影響你對(duì)整棵樹(shù)訪問(wèn)順序的理解容易把后面的題也帶偏。我在第一次刷這道題時(shí)其實(shí)沒(méi)有立刻想到這里而是直接背代碼。后來(lái)做“二叉樹(shù)的層序遍歷 II”從葉子到根輸出每層的時(shí)候才意識(shí)到“鎖定 size 逐層處理”是一個(gè)通用模板它能解決所有層序相關(guān)的問(wèn)題。所以我的建議是把這段 BFS 模板刻在腦子里不只是為了這一題而是為了后面那三四道層序變體題。3. 遞歸 DFS另一種更優(yōu)雅的解法但坑也更多3.1 為什么右視圖可以用先序遍歷來(lái)寫(xiě)先用 DFS 寫(xiě)最核心的思路是遞歸時(shí)先訪問(wèn)右子樹(shù)再訪問(wèn)左子樹(shù)。當(dāng)遞歸深度 depth 第一次等于當(dāng)前結(jié)果數(shù)組的長(zhǎng)度時(shí)說(shuō)明這是這一層第一次被訪問(wèn)到的節(jié)點(diǎn)由于我們先走右子樹(shù)這個(gè)節(jié)點(diǎn)一定是最右側(cè)的那個(gè)。換句話說(shuō)DFS 版本依賴一個(gè)隱藏條件同一深度下先被訪問(wèn)到的節(jié)點(diǎn)就是該層最右邊的節(jié)點(diǎn)。所以遞歸的參數(shù)要帶depth結(jié)果數(shù)組ans的長(zhǎng)度天然對(duì)應(yīng)已經(jīng)“看到”過(guò)的層級(jí)數(shù)。如果depth ans.size()說(shuō)明當(dāng)前層還沒(méi)有記錄任何節(jié)點(diǎn)那當(dāng)前節(jié)點(diǎn)就是這一層的右視圖節(jié)點(diǎn)。這里有個(gè)容易暈的點(diǎn)DFS 的遞歸順序是“根 - 右子樹(shù) - 左子樹(shù)”但很多人寫(xiě)的時(shí)候習(xí)慣先寫(xiě)左再寫(xiě)右結(jié)果最后得到的視圖變成了左視圖或者亂序。所以我建議記一個(gè)口訣右視圖先右后左左視圖先左后右。換言之你想從哪邊看就把哪邊的遞歸調(diào)用寫(xiě)在前面。這個(gè)解法的優(yōu)點(diǎn)很明顯不需要額外的隊(duì)列空間空間復(fù)雜度取決于樹(shù)的深度遞歸棧深度。缺點(diǎn)也很明顯遞歸深度如果很大極端情況下比如樹(shù)退化成一個(gè)鏈可能會(huì)爆棧。這一點(diǎn)在 LeetCode 上大多數(shù)測(cè)試用例不會(huì)踩到但在面試中如果你主動(dòng)提出來(lái)會(huì)加分不少。3.2 DFS 代碼實(shí)操C 遞歸版class Solution { public: void dfs(TreeNode* root, int depth, vectorint ans) { if (!root) return; if (depth ans.size()) { // 這一層第一次訪問(wèn)到且一定是最右節(jié)點(diǎn) ans.push_back(root-val); } dfs(root-right, depth 1, ans); // 先右 dfs(root-left, depth 1, ans); // 后左 } vectorint rightSideView(TreeNode* root) { vectorint ans; dfs(root, 0, ans); return ans; } };這里depth從 0 開(kāi)始。如果根節(jié)點(diǎn)不為空第一次進(jìn)入時(shí)depth 0ans.size() 0條件成立把根節(jié)點(diǎn)放進(jìn)答案。然后進(jìn)入右子樹(shù)此時(shí)depth 1如果右子樹(shù)不為空且ans.size() 1條件成立把右子樹(shù)的根放進(jìn)去。如果右子樹(shù)為空則遞歸左子樹(shù)此時(shí)左子樹(shù)的根就是第二層最右邊的節(jié)點(diǎn)了。這個(gè)邏輯妙就妙在它不關(guān)心當(dāng)前層到底有多少節(jié)點(diǎn)只關(guān)心“這一層的第一個(gè)被訪問(wèn)節(jié)點(diǎn)”。由于先遞歸右子樹(shù)所以第一個(gè)被訪問(wèn)的一定是最右邊的節(jié)點(diǎn)。但有個(gè)細(xì)節(jié)需要注意ans.size()是全局的也就是說(shuō)如果右子樹(shù)不存在左子樹(shù)會(huì)把第二層“補(bǔ)上”如果右子樹(shù)存在但左子樹(shù)更深左子樹(shù)里更深層的節(jié)點(diǎn)也會(huì)被正確記錄。因?yàn)檫f歸是深度驅(qū)動(dòng)每一層只會(huì)記錄一次。這跟 BFS 的“每層取最后一個(gè)”在結(jié)果上是完全一致的。3.3 BFS 和 DFS到底選哪個(gè)面試的時(shí)候我建議兩層都提。先給 BFS因?yàn)樗庇^、不容易出錯(cuò)然后說(shuō)“其實(shí)也可以用 DFS 寫(xiě)思路是先右后左配合深度判斷”。這樣一來(lái)你既展示了基礎(chǔ)能力又展示了思維的靈活性。從實(shí)際應(yīng)用場(chǎng)景來(lái)說(shuō)如果題目只是求右視圖BFS 更容易寫(xiě)對(duì)也不容易爆棧推薦優(yōu)先。如果題目需要你同時(shí)輸出左視圖和右視圖DFS 可以在一趟遞歸里分別處理兩個(gè)方向代碼更緊湊。如果樹(shù)的深度可能非常大比如 10 萬(wàn)層的鏈表結(jié)構(gòu)BFS 的隊(duì)列空間是 O(width)DFS 的遞歸棧是 O(height)兩者在極端情況下都可能有風(fēng)險(xiǎn)但 BFS 更可控因?yàn)殛?duì)列不會(huì)觸發(fā)系統(tǒng)棧溢出。所以我的建議是面試默認(rèn)先寫(xiě) BFS再在追問(wèn)下補(bǔ)充 DFS。你要是直接寫(xiě) DFS也行但一定要明確說(shuō)出“遞歸深度可能帶來(lái)?xiàng)Ｒ绯鲲L(fēng)險(xiǎn)”這個(gè)權(quán)衡。這兩個(gè)解法的復(fù)雜度都是 O(n)一個(gè)在時(shí)間上一個(gè)都不能省沒(méi)有誰(shuí)壓倒誰(shuí)。4. 寫(xiě)二叉樹(shù)程序?yàn)槭裁纯偸菆?bào)運(yùn)行時(shí)錯(cuò)誤從這道題看常見(jiàn)坑熱詞里出現(xiàn)頻率最高的就是這句話——“寫(xiě)二叉樹(shù)程序時(shí)為什么總是報(bào)運(yùn)行時(shí)錯(cuò)誤”。這個(gè)問(wèn)題我在群里被問(wèn)了無(wú)數(shù)遍尤其新人刷 hot100 二叉樹(shù)的題報(bào)錯(cuò)基本上都是以下幾個(gè)原因之一。我結(jié)合 199 題的實(shí)際場(chǎng)景把最典型的幾類(lèi)列出來(lái)對(duì)照著排查大部分問(wèn)題都能當(dāng)場(chǎng)解決。4.1 空指針訪問(wèn)二叉樹(shù)報(bào)錯(cuò)的頭號(hào)元兇二叉樹(shù)題里最經(jīng)典也最冤的錯(cuò)誤就是訪問(wèn)了NULL - left或NULL - right。比如這樣一段代碼if (node-left) q.push(node-left); if (node-right) q.push(node-right);如果你忘了判斷node本身是否為空那么在node為NULL時(shí)node-left就是一次空指針解引用運(yùn)行時(shí)直接段錯(cuò)誤。還有一個(gè)隱蔽版本遞歸 DFS 里如果 base case 沒(méi)寫(xiě)好或者root傳入時(shí)就是空指針那么函數(shù)一開(kāi)始的if (!root) return;就缺失了繼續(xù)往下走就會(huì)崩。不光是 199所有二叉樹(shù)題目排查的第一步都是檢查所有可能為空的指針是否都判空了。包括遞歸入口、左右子樹(shù)入隊(duì)、左右子樹(shù)遞歸調(diào)用。4.2 循環(huán)邊界寫(xiě)錯(cuò)把 size 看成動(dòng)態(tài)值剛才說(shuō)過(guò)BFS 里必須先把int size q.size();存下來(lái)。如果你在循環(huán)里直接用了q.size()每一輪彈出和壓入都會(huì)改變它循環(huán)次數(shù)就會(huì)失控輕則結(jié)果錯(cuò)誤重則死循環(huán)或越界訪問(wèn)。我見(jiàn)過(guò)很多人這樣寫(xiě)for (int i 0; i q.size(); i) { // ... q.push(node-left); // q.size() 又變大了 }只要隊(duì)列里還有節(jié)點(diǎn)這個(gè)循環(huán)就永遠(yuǎn)結(jié)束不了最后可能出現(xiàn) vector 越界或者隊(duì)列無(wú)限增長(zhǎng)。這種 bug 非常難用肉眼發(fā)現(xiàn)因?yàn)樗辉谶\(yùn)行時(shí)報(bào)錯(cuò)而且報(bào)錯(cuò)位置常常在 STL 內(nèi)部不是你的業(yè)務(wù)代碼。排查技巧看到“heap-buffer-overflow”或“AddressSanitizer”報(bào)錯(cuò)優(yōu)先懷疑所有的循環(huán)邊界條件尤其是用了動(dòng)態(tài) size 的地方。4.3 遞歸棧溢出樹(shù)退化成長(zhǎng)鏈如果你用 DFS 解法而樹(shù)恰好是一個(gè)左單支或者右單支比如每個(gè)節(jié)點(diǎn)只有右孩子遞歸深度就是節(jié)點(diǎn)個(gè)數(shù) N。當(dāng) N 超過(guò)系統(tǒng)棧大小通常是幾萬(wàn)到幾十萬(wàn)層時(shí)程序會(huì)直接爆棧退出報(bào)“stack overflow”。這種情況并不罕見(jiàn)LeetCode 的測(cè)試數(shù)據(jù)不一定包含極端情況但如果你自己構(gòu)造一條 10 萬(wàn)層的鏈DFS 就會(huì)當(dāng)場(chǎng)崩潰。解決方案改用 BFS或者把遞歸改寫(xiě)成顯式棧的迭代 DFS。顯式棧雖然代碼長(zhǎng)一點(diǎn)但?？臻g在堆上可以承受更大的深度。4.4 STL 容器使用不當(dāng)空隊(duì)列取 front() / pop()這也是一個(gè)特別常見(jiàn)的坑。層序遍歷中如果根節(jié)點(diǎn)為空你沒(méi)有提前判空就q.front()隊(duì)列是空的調(diào)用 front() 是未定義行為在 LeetCode 上會(huì)觸發(fā)運(yùn)行時(shí)錯(cuò)誤而在本地編譯器上可能“碰巧”不出來(lái)。具體到 199 題如果你寫(xiě)成queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); // 如果 root 為 NULLq 不為空但 node 是 NULL q.pop(); // 下面沒(méi)有對(duì) node 判空就直接 node-left }注意這里隊(duì)列不一定為空但隊(duì)列里存的是 NULL 指針。front()返回的是一個(gè)空指針訪問(wèn)node-left照樣崩。所以最穩(wěn)妥的寫(xiě)法是先判root NULL再入隊(duì)在訪問(wèn)節(jié)點(diǎn)前再判一次該節(jié)點(diǎn)是否為空。雙重保險(xiǎn)不嫌多。4.5 排查二叉樹(shù)運(yùn)行時(shí)錯(cuò)誤的實(shí)戰(zhàn)順序我自己的排查順序是固定的你可以直接抄作業(yè)先看報(bào)錯(cuò)類(lèi)型stack overflow 優(yōu)先懷疑遞歸過(guò)深heap-buffer-overflow / segfault 優(yōu)先懷疑空指針或下標(biāo)越界。檢查所有-left/-right/-val之前有沒(méi)有判空。檢查 BFS 循環(huán)里有沒(méi)有把size寫(xiě)成動(dòng)態(tài)值。檢查遞歸 base case 是否覆蓋了空節(jié)點(diǎn)和葉子節(jié)點(diǎn)兩種情況。檢查 vector / 數(shù)組下標(biāo)是否可能越界尤其是ans[depth]這種寫(xiě)法199 題里一般不建議用下標(biāo)直接賦值用 push_back 更安全。本地調(diào)試時(shí)打印每一步訪問(wèn)的節(jié)點(diǎn)值和深度肉眼確認(rèn)遍歷順序是否符合預(yù)期。這張速查表請(qǐng)重點(diǎn)收藏報(bào)錯(cuò)類(lèi)型常見(jiàn)原因?qū)?yīng)排查方向segmentation fault空指針解引用檢查所有 node 判空stack overflow遞歸深度過(guò)大改迭代或顯式棧heap-buffer-overflowSTL 容器越界檢查循環(huán)邊界、vector 下標(biāo)死循環(huán) / 超時(shí)BFS 中 size 動(dòng)態(tài)變化先存 size再 for 固定層數(shù)結(jié)果錯(cuò)亂遞歸順序?qū)懛从乙晥D必須先右后左5. 面試追問(wèn)從右視圖到視圖類(lèi)題型的延展單元測(cè)試過(guò)了以后面試官通常不會(huì)就這么放你走他會(huì)開(kāi)始追問(wèn)。最常見(jiàn)的是這三類(lèi)一是讓你說(shuō)說(shuō)兩版解法的復(fù)雜度二是讓你改成左視圖或二叉樹(shù)的俯視圖三是把“右視圖”變成“層序輸出所有節(jié)點(diǎn)”。5.1 復(fù)雜度分析怎么說(shuō)才專(zhuān)業(yè)BFS 版時(shí)間 O(n)每個(gè)節(jié)點(diǎn)恰好入隊(duì)出隊(duì)一次空間 O(n)隊(duì)列最多同時(shí)容納一層的節(jié)點(diǎn)數(shù)最壞情況是滿二叉樹(shù)的最后一層節(jié)點(diǎn)數(shù)約 n/2。DFS 版時(shí)間 O(n)每個(gè)節(jié)點(diǎn)恰好訪問(wèn)一次空間 O(h)h 是樹(shù)的高度。最壞情況 h n鏈狀樹(shù)最好情況 h log n滿二叉樹(shù)。一個(gè)容易丟分的點(diǎn)很多人說(shuō)遞歸空間是 O(n)其實(shí)不夠精確。準(zhǔn)確說(shuō)是 O(h)如果樹(shù)是鏈狀O(h) O(n)如果不是鏈狀O(h) 會(huì)小于 O(n)。這個(gè)區(qū)別面試官一眼就看出來(lái)了。5.2 左視圖、俯視圖、層序遍歷變體左視圖怎么寫(xiě)很多人說(shuō)“右視圖改成左視圖只要把層序里每層取最后一個(gè)改成取第一個(gè)”。這個(gè)說(shuō)法沒(méi)問(wèn)題但不全面。如果按這個(gè)思路改入隊(duì)順序不變?nèi)〉谝粋€(gè)即可。但如果你想用 DFS 寫(xiě)左視圖遞歸順序就要改成先左后右條件仍然是depth ans.size()。這樣才符合“優(yōu)先訪問(wèn)最左邊節(jié)點(diǎn)”的邏輯。那俯視圖呢這是另一道經(jīng)典題?？途W(wǎng)上很多LeetCode 上也有類(lèi)似題它要求你從上往下、從左到右輸出每一層第一個(gè)看到的節(jié)點(diǎn)。這個(gè)就不能只用層序了需要記錄每個(gè)節(jié)點(diǎn)的水平坐標(biāo)然后對(duì)同一水平坐標(biāo)的節(jié)點(diǎn)只保留最上面的。這就是“視圖類(lèi)”題型的進(jìn)階版用到了哈希表和排序復(fù)雜度從 O(n) 變成了 O(n log n)。如果你能把右視圖從 BFS 到 DFS 都搞清楚再做俯視圖思路會(huì)清晰很多因?yàn)楸举|(zhì)上都是“某一維度下的第一個(gè)節(jié)點(diǎn)”問(wèn)題。5.3 迭代 DFS 怎么寫(xiě)不用遞歸也優(yōu)雅如果你面試時(shí)主動(dòng)提到“遞歸有爆棧風(fēng)險(xiǎn)我可以改成迭代”那一瞬間你的印象分會(huì)拉高不少。迭代 DFS 的寫(xiě)法基于顯式棧class Solution { public: vectorint rightSideView(TreeNode* root) { vectorint ans; if (!root) return ans; stackpairTreeNode*, int stk; stk.push({root, 0}); while (!stk.empty()) { auto [node, depth] stk.top(); stk.pop(); if (!node) continue; if (depth ans.size()) { ans.push_back(node-val); } stk.push({node-left, depth 1}); // 注意壓棧順序 stk.push({node-right, depth 1}); // 右子樹(shù)后進(jìn)棧先處理 } return ans; } };這里的關(guān)鍵點(diǎn)棧是后進(jìn)先出所以我們先把左子樹(shù)壓入棧再把右子樹(shù)壓入棧。這樣一來(lái)右子樹(shù)會(huì)先被彈出并處理從而保證了同一層里右子樹(shù)先被訪問(wèn)depth ans.size()的判斷邏輯依然成立。提示如果把壓棧順序反過(guò)來(lái)會(huì)得到左視圖這一點(diǎn)可以自己試一下。寫(xiě)迭代 DFS 的時(shí)候最容易錯(cuò)的不是 stack 操作而是棧的訪問(wèn)順序和遞歸順序不一致。只要記住“想先訪問(wèn)誰(shuí)就讓誰(shuí)后入棧”就不會(huì)亂。6. 一行小技巧如何用狀態(tài)壓縮省掉 depth 參數(shù)最后再分享一個(gè)小技巧。BFS 版本里可以不用帶 depth因?yàn)槊繉拥倪吔缫呀?jīng)由for (int i 0; i size; i)決定了。但 DFS 版本如果不想帶 depth 參數(shù)還有一種做法遞歸時(shí)把a(bǔ)ns.size()作為隱含深度判斷。什么意思呢你可以把遞歸函數(shù)定義成int dfs(TreeNode* root, int depth, vectorint ans) { if (!root) return depth; if (depth ans.size()) ans.push_back(root-val); return max(dfs(root-right, depth 1, ans), dfs(root-left, depth 1, ans)); }但這樣寫(xiě)其實(shí)沒(méi)有意義因?yàn)?depth 還是要傳。我真正想說(shuō)的是你不需要讓遞歸函數(shù)返回深度直接在遞歸內(nèi)部判斷depth ans.size()就夠了。這個(gè)“用數(shù)組長(zhǎng)度代表已訪問(wèn)層數(shù)”的思路很多樹(shù)的題目都能用到尤其是輸出“每一層的第一個(gè)節(jié)點(diǎn)”這類(lèi)題。我個(gè)人在實(shí)際刷題中的體會(huì)是199 這道題第一次接觸的人常常覺(jué)得 BFS 解法才是“正宗”不太理解 DFS 解法為什么也能得到正確答案。其實(shí)兩種方法從不同角度回答了同一個(gè)問(wèn)題——BFS 是從橫向切面找最右點(diǎn)DFS 是從縱向路徑找第一個(gè)到達(dá)該層的點(diǎn)。吃透這一題對(duì)后續(xù)理解二叉樹(shù)的深度、層序、視圖類(lèi)問(wèn)題會(huì)有很大幫助。我在 hot100 做題時(shí)養(yǎng)成的習(xí)慣是每道題都寫(xiě)兩種解法并用一個(gè)極端用例和一個(gè)空用例去測(cè)。右視圖這一題我會(huì)用空樹(shù)測(cè)試返回[]用單節(jié)點(diǎn)樹(shù)測(cè)試返回[root.val]再用鏈狀樹(shù)測(cè)試是否會(huì)爆棧。這些邊界情況在面試時(shí)都是加分項(xiàng)。