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