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