1. 先把五行代碼的“血緣關(guān)系”理清楚刷LeetCode的朋友應(yīng)該都有過這樣一種體驗今天刷了144題前序遍歷AC了感覺很簡單明天做94題中序遍歷也AC了覺得不過如此后天碰到145題后序遍歷順手就寫完了——然后第102題層序遍歷直接懵了第111題最小深度又開始懷疑自己到底懂不懂二叉樹。這五道題放在一起刷其實挺有講究的。它們恰好覆蓋了二叉樹最核心的幾種遍歷方式前序、中序、后序?qū)儆谏疃葍?yōu)先搜索DFS的范疇層序?qū)儆趶V度優(yōu)先搜索BFS的范疇而最小深度這道題表面上考查的是樹的深度計算實際上把DFS和BFS兩條路線都串起來了?？梢哉f二叉樹遍歷的遞歸模板、迭代棧寫法、隊列層序遍歷技巧以及邊界條件判斷全都濃縮在這五道題里。這篇文章我從頭到尾把這五道題串一遍不講虛的直接給代碼、給執(zhí)行過程、給踩坑點(diǎn)。不管你用的是C、Java還是Python思路是通用的。寫完之后你會發(fā)現(xiàn)二叉樹的遍歷根本不是靠背模板而是靠理解“節(jié)點(diǎn)訪問時機(jī)”和“棧/隊列的入出順序”。1.1 前序、中序、后序命名規(guī)則已經(jīng)告訴你全部信息先看最基礎(chǔ)的定義。二叉樹的前序、中序、后序遍歷三個名字里的“前”“中”“后”指的是根節(jié)點(diǎn)被訪問的位置前序遍歷根節(jié)點(diǎn) → 左子樹 → 右子樹根在前中序遍歷左子樹 → 根節(jié)點(diǎn) → 右子樹根在中間后序遍歷左子樹 → 右子樹 → 根節(jié)點(diǎn)根在后這三個順序是對“根節(jié)點(diǎn)”而言的。左子樹永遠(yuǎn)在右子樹之前這一點(diǎn)不變。所以記的時候不需要死記“前中后”只需要記住根在哪前序先輸出根再遞歸左再遞歸右。中序先遞歸左再輸出根再遞歸右。后序先遞歸左再遞歸右最后輸出根。一句話總結(jié)根的位置決定了遍歷的名字。你只要把根放到對應(yīng)位置整棵樹的輸出順序就對了。1.2 層序和最小深度從“縱向”到“橫向”的思路切換層序遍歷Level Order Traversal是另一種維度的遍歷。DFS系列是一路走到葉子再返回BFS層序遍歷則是從上到下、從左到右一層一層地掃過去。比如這樣一棵樹3 / \ 9 20 / \ 15 7前序輸出是 3, 9, 20, 15, 7層序輸出是 [3], [9, 20], [15, 7]每一層單獨(dú)成一組。這個“按層分組”的特性是第102題的關(guān)鍵。第111題最小深度屬于“二叉樹深度/高度”這類問題。套路上可以遞歸來做也可以配合層序BFS來做而且BFS在這道題上有天然的效率優(yōu)勢——因為BFS一旦碰到第一個葉子節(jié)點(diǎn)就能立刻返回當(dāng)前層數(shù)。這個優(yōu)化在面試?yán)锪钠饋砗芗臃帧?. 遞歸解法三行代碼解決前中后序遞歸是二叉樹的“母語”。因為二叉樹本身就是遞歸定義的左子樹是一棵樹右子樹也是一棵樹。所以用遞歸去遍歷二叉樹邏輯最直觀代碼也最短。2.1 遞歸三要素終止條件、遞歸調(diào)用、操作時機(jī)寫二叉樹的遞歸其實只需要記住一個模板void traverse(TreeNode* root) { // 終止條件 if (root nullptr) return; // 前序位置先訪問根 traverse(root-left); // 中序位置左子樹遍歷完訪問根 traverse(root-right); // 后序位置左右子樹都遍歷完訪問根 }你發(fā)現(xiàn)沒有前序、中序、后序的代碼結(jié)構(gòu)完全一樣區(qū)別僅僅在于“操作根節(jié)點(diǎn)”的語句放在哪個位置。放在最前面就是前序放在中間就是中序放在最后面就是后序。這就是“訪問時機(jī)”的核心意義。很多初學(xué)者寫遞歸會卡在“為什么這個遞歸過程和我手動模擬的不一樣”。原因在于遞歸是借助系統(tǒng)調(diào)用棧完成的。你調(diào)用 traverse(root-left) 的時候當(dāng)前函數(shù)的狀態(tài)會被壓棧保存等左子樹全部執(zhí)行完棧頂彈出回到當(dāng)前節(jié)點(diǎn)繼續(xù)往下走。理解這一點(diǎn)后面看迭代法就輕松了。2.2 完整代碼實現(xiàn)與執(zhí)行軌跡第144題前序遍歷C寫法void preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); // 前序先訪問根 preorder(root-left, res); // 再左 preorder(root-right, res); // 后右 } vectorint preorderTraversal(TreeNode* root) { vectorint res; preorder(root, res); return res; }第94題中序遍歷void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); // 先左 res.push_back(root-val); // 中序再訪問根 inorder(root-right, res); // 后右 } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; }第145題后序遍歷void postorder(TreeNode* root, vectorint res) { if (!root) return; postorder(root-left, res); // 先左 postorder(root-right, res); // 再右 res.push_back(root-val); // 后序最后訪問根 } vectorint postorderTraversal(TreeNode* root) { vectorint res; postorder(root, res); return res; }用一棵小樹手動走一遍前序遍歷root 1左子節(jié)點(diǎn) 2右子節(jié)點(diǎn) 3其中 2 沒有子節(jié)點(diǎn)3 的左子節(jié)點(diǎn) 4。1 / \ 2 3 / 4前序遍歷的執(zhí)行過程是訪問 1 → 進(jìn)入 2訪問 2→ 2 的左右為空返回 → 進(jìn)入 3訪問 3→ 進(jìn)入 4訪問 4→ 4 返回 → 3 返回 → 結(jié)束。輸出1, 2, 3, 4。中序則是進(jìn)入 2左空訪問 2→ 返回 → 訪問 1 → 進(jìn)入 3 → 進(jìn)入 4訪問 4→ 返回 → 訪問 3 → 輸出2, 1, 4, 3。后序輸出2, 4, 3, 1。2.3 遞歸解法的局限不僅棧溢出還有效率問題遞歸雖然好寫但有兩個問題。第一個是樹深度很大時系統(tǒng)?？赡芤绯?。LeetCode上雖然一般不會讓遞歸爆棧但面試官一定會問“遞歸的缺點(diǎn)是什么”提前想好這一點(diǎn)非常有價值。第二個問題是遞歸過程中有大量函數(shù)調(diào)用開銷。這個在LeetCode的測試數(shù)據(jù)里體現(xiàn)不出來但在真實業(yè)務(wù)場景中如果一棵樹有幾萬甚至幾十萬個節(jié)點(diǎn)遞歸的性能瓶頸就出來了。所以掌握迭代法是必須的這不只是面試題也是實操中構(gòu)建健壯代碼的能力。3. 迭代解法用顯式棧還原遞歸過程迭代法的思路是用一個顯式棧std::stack來模擬遞歸調(diào)用時的系統(tǒng)棧。理解了遞歸的執(zhí)行順序再來看迭代法你會發(fā)現(xiàn)整個過程就是“把遞歸調(diào)用棧手動寫出來”。3.1 前序遍歷根先出先壓右再壓左前序的順序是“根 → 左 → 右”。用棧實現(xiàn)時因為棧是后進(jìn)先出所以入棧時要先壓右子節(jié)點(diǎn)再壓左子節(jié)點(diǎn)這樣左子節(jié)點(diǎn)才會先被彈出。vectorint preorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return res; }這個思路一句話概括彈一個訪問一個把右左依次入棧。很多人寫錯的地方是入棧順序記反了就變成“根右左”了。3.2 中序遍歷一路向左彈出訪問轉(zhuǎn)右繼續(xù)中序比前序稍微復(fù)雜一點(diǎn)因為順序是“左 → 根 → 右”你不能一開始就把根彈出去訪問需要先一路向左壓棧直到左子樹為空再彈出訪問然后轉(zhuǎn)向右子樹。vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { // 一路向左壓棧 while (cur) { st.push(cur); cur cur-left; } // 彈出訪問 cur st.top(); st.pop(); res.push_back(cur-val); // 轉(zhuǎn)向右子樹 cur cur-right; } return res; }這里最關(guān)鍵的變量是cur它代表“當(dāng)前需要處理的節(jié)點(diǎn)”。第一個內(nèi)層 while 把左鏈全部壓棧然后彈出一個訪問再讓cur指向右子樹。右子樹同樣會進(jìn)入內(nèi)層 while 把它的左鏈壓棧。這個過程完整模擬了遞歸中“進(jìn)入左子樹 → 訪問根 → 進(jìn)入右子樹”的步驟。3.3 后序遍歷兩個棧的思路或者一個棧加反轉(zhuǎn)后序的順序是“左 → 右 → 根”。直接用一個棧模擬會遇到一個問題根節(jié)點(diǎn)被彈出來時還不到訪問時機(jī)因為要等右子樹處理完才能訪問。所以后序的迭代實現(xiàn)是三種遍歷里最容易出錯的。一個經(jīng)典的技巧是用類似前序的思路先得到“根 → 右 → 左”的順序然后反轉(zhuǎn)。vectorint postorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); // 注意先壓左再壓右這樣先彈出的是右 if (node-left) st.push(node-left); if (node-right) st.push(node-right); } reverse(res.begin(), res.end()); return res; }這段代碼的邏輯是前序版本是“根 → 左 → 右”這里把壓棧順序反過來先壓左再壓右彈出的順序就變成了“根 → 右 → 左”。最后整體反轉(zhuǎn)得到“左 → 右 → 根”也就是后序。注意最后一步 reverse 是 O(n) 時間整體時間復(fù)雜度仍然是 O(n)空間復(fù)雜度 O(n)沒毛病。3.4 三種迭代對比什么時候該用哪種寫法遍歷方式核心思路入棧/處理順序易錯點(diǎn)前序彈一個訪問一個右左入棧右 → 左入棧順序?qū)懛粗行蛞宦废蜃髩簵椩L問轉(zhuǎn)右左鏈路壓棧忘記 cur cur-right后序前序變體 反轉(zhuǎn)左 → 右 入棧反轉(zhuǎn)結(jié)果壓棧順序和前序相反實際上中序和后續(xù)的迭代寫法還有更“統(tǒng)一”的版本比如給棧里壓入帶標(biāo)記的節(jié)點(diǎn)visited1表示該訪問了這里就不展開——如果面試官要求不用反轉(zhuǎn)寫出后序可以用一個prev指針記錄上一個訪問的節(jié)點(diǎn)或者用雙棧法。不過個人經(jīng)驗是后序的反轉(zhuǎn)法是最不容易寫錯的面試時優(yōu)先保證正確性。4. 第102題層序遍歷BFS隊列的標(biāo)準(zhǔn)用法層序遍歷和前中后序不是一類問題它走的是廣度優(yōu)先借用隊列一層一層往外掃。4.1 基礎(chǔ)BFS模板隊列 循環(huán)大多數(shù)人的第一版層序代碼長這樣vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; // 處理當(dāng)前層 for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }這里最關(guān)鍵的一行是int size q.size()。它必須在 for 循環(huán)之前取因為隊列在循環(huán)過程中會不斷加入下一層的節(jié)點(diǎn)q.size()會變化。提前取好sizefor 循環(huán)只處理當(dāng)前層已有的節(jié)點(diǎn)下一層的節(jié)點(diǎn)自然留在隊列里為下一輪外層循環(huán)做準(zhǔn)備。4.2 為什么要按層分組從一維輸出到二維輸出第102題要求的輸出是一個二維數(shù)組每個子數(shù)組是某一層的節(jié)點(diǎn)。所以你會看到代碼里多了一個vectorint level每一層單獨(dú)收集再 push 到結(jié)果。如果換成蛇形走位Z字形輸出只需要加一個層號判斷偶數(shù)層從左到右奇數(shù)層從右到左翻轉(zhuǎn)一下level即可。這道題還有個常見的變體是“二叉樹的右視圖”。思路也是層序只是每層只取最后一個節(jié)點(diǎn)。理解了按層分組的模板這些變體基本是半小時內(nèi)能拿下的量。4.3 層序變體一網(wǎng)打盡二叉樹的層序遍歷 II自底向上BFS 結(jié)束后 reverse 整個res。二叉樹的鋸齒形層序遍歷根據(jù)層號奇偶決定是否反轉(zhuǎn)level。二叉樹的右視圖每層取level.back()。填充每個節(jié)點(diǎn)的下一個右側(cè)節(jié)點(diǎn)指針層序遍歷時用前一個節(jié)點(diǎn)pre-next cur。這些都建立在同一個 BFS 模板上。所以第102題不只是背模板理解“當(dāng)前層節(jié)點(diǎn)數(shù)量在進(jìn)入循環(huán)前鎖定”這個思想后面的變體題都能換湯不換藥地解決。5. 第111題最小深度DFS與BFS的抉擇第111題要求返回二叉樹的最小深度這里的深度是指從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)。注意幾個關(guān)鍵字葉子節(jié)點(diǎn)、最近、節(jié)點(diǎn)數(shù)。這三者缺一不可。5.1 遞歸寫法最容易忽略的“單子樹為空”場景最小深度的遞歸直覺寫法是左子樹最小深度和右子樹最小深度取較小值再加1。對應(yīng)代碼int minDepth(TreeNode* root) { if (!root) return 0; int left minDepth(root-left); int right minDepth(root-right); return min(left, right) 1; }看起來沒問題但跑測試就會發(fā)現(xiàn)對于一個只有左子樹的節(jié)點(diǎn)上面代碼會返回 1——這是錯的。比如下面這棵樹1 / 2根節(jié)點(diǎn) 1 沒有右子樹所以right 0min(1, 0) 1 1。但根節(jié)點(diǎn) 1 不是葉子節(jié)點(diǎn)所以最小深度不可能是 1應(yīng)該是 2。原因在于當(dāng)一個節(jié)點(diǎn)只有左子樹或只有右子樹時空的那一側(cè)不能參與最小深度比較。正確寫法int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left) return minDepth(root-right) 1; if (!root-right) return minDepth(root-left) 1; return min(minDepth(root-left), minDepth(root-right)) 1; }這算是題意理解的一個小坑但實際面試中問“最小深度”十有八九會碰到這個陷阱。關(guān)鍵判斷依據(jù)是空節(jié)點(diǎn)不算葉子所以不存在“空子樹深度為0參與比較”這回事。5.2 BFS解法找到第一個葉子節(jié)點(diǎn)就返回BFS 解法與上述 DFS 的遞歸寫法思路不同層序遍歷從上到下掃當(dāng)碰到第一個“左右子節(jié)點(diǎn)都為空”的節(jié)點(diǎn)時當(dāng)前層數(shù)就是最小深度。由于 BFS 是一層一層掃的第一次遇到葉子節(jié)點(diǎn)一定是在最小深度那一層。int minDepth(TreeNode* root) { if (!root) return 0; queuepairTreeNode*, int q; q.push({root, 1}); while (!q.empty()) { auto [node, depth] q.front(); q.pop(); if (!node-left !node-right) return depth; if (node-left) q.push({node-left, depth 1}); if (node-right) q.push({node-right, depth 1}); } return 0; }也可以沿用層序模板用level記錄當(dāng)前層數(shù)。BFS 的優(yōu)點(diǎn)在這個問題里非常明顯一旦找到葉子節(jié)點(diǎn)就立刻返回不需要遍歷整棵樹。對于一棵很“偏”的樹最壞情況是 BFS 退化成遍歷整棵樹復(fù)雜度仍是 O(n)但平均情況下 BFS 往往比 DFS 更早返回。5.3 最大深度 vs 最小深度一個容易混淆的點(diǎn)最大深度用 DFS 遞歸寫起來就簡單得多不會有人寫錯max(left, right) 1。最大和最小的區(qū)別在于最大深度可以用空子樹返回 0 來參與比較因為max(0, 1) 1不影響正確性最小深度則不行因為min(0, 1) 0會直接吞掉另一側(cè)的實際深度。理解了這個邏輯你就能從“背題”升級到“懂題”。6. 實戰(zhàn)中的邊界條件與常見坑位五道題刷一遍容易但會犯的錯基本都集中在邊界條件上。這里我按踩坑頻率從高到低列一遍都是真實刷題和面試中見過的問題。6.1 空樹任何遍歷的第一步都是判空幾乎每一道二叉樹題目的遞歸版本開頭都是if (!root) return ...。迭代版本則要在開始時就判斷if (!root) return ...否則訪問root-val直接空指針異常。尤其是在層序和最小深度題里空樹返回的應(yīng)該是空數(shù)組或 0千萬別把空指針推進(jìn)隊列。6.2 隊列和棧里存的是什么節(jié)點(diǎn)本身還是包裝對象層序遍歷 BFS 的隊列queueTreeNode*存的是節(jié)點(diǎn)指針第111題的最小深度 BFS 版本存的是pairTreeNode*, int用來同時記錄節(jié)點(diǎn)和層數(shù)。有些同學(xué)圖省事只存int depth那你就丟失了節(jié)點(diǎn)信息根本沒法繼續(xù)遍歷。分清容器里存的東西是你代碼能否跑通的關(guān)鍵。實際上還有一種更巧的寫法是每層用一個for循環(huán)depth在外層循環(huán)中加1隊列只存節(jié)點(diǎn)。這種寫法在代碼上更統(tǒng)一。6.3 遞歸和迭代的時間/空間復(fù)雜度解法時間復(fù)雜度空間復(fù)雜度遞歸調(diào)用棧/棧/隊列遞歸 DFSO(n)O(h)h 為樹高迭代 DFSO(n)O(h)層序 BFSO(n)O(n)最壞情況是一層能放 n/2 個節(jié)點(diǎn)在 LeetCode 的題解討論區(qū)很多人只關(guān)注時間復(fù)雜度是 O(n)但空間復(fù)雜度的分析一樣是面試必問。遞歸的空間復(fù)雜度是調(diào)用棧的深度也就是樹的高度如果樹退化成鏈表h n就會 O(n) 空間。6.4 調(diào)試技巧如何用一個小輸入驗證代碼二叉樹的題目調(diào)試有一個非常高效的方法用最小測試用例逐步走查。比如用一個只有根節(jié)點(diǎn)的樹、一個只有左子樹的樹、一個空樹分別跑一遍前中后序、層序、最小深度。這三個用例能擋住 90% 的邊界錯誤。另外寫代碼前先自己在紙上把樹畫出來標(biāo)出預(yù)期遍歷順序再跑代碼對照。我見過太多同學(xué)上來就刷題連前序和后序輸出到底差在哪都沒想清楚代碼寫錯了也不知道。如果面試時被要求“手動模擬一遍算法流程”畫圖 口頭模擬的能力比代碼本身更讓面試官眼前一亮。7. 從五道題到一套通用方法論五道題刷完回頭看它們其實在鍛煉同一套能力你把一棵樹抽象成一個數(shù)據(jù)流然后用某種方式把數(shù)據(jù)流里的元素拿出來。7.1 判空、遞歸、棧模擬、隊列模擬套路萬變不離其宗遞歸解法依賴系統(tǒng)棧迭代解法依賴顯式棧。DFS前中后序的本質(zhì)是“先深入再回溯”用?；蜻f歸實現(xiàn)。BFS層序的本質(zhì)是“逐層擴(kuò)散”用隊列實現(xiàn)。最小深度的 DFS 版本要處理單子樹為空BFS 版本則找到葉子即返回。這套方法論不只能解決二叉樹題。當(dāng)你去做圖的遍歷、拓?fù)渑判?、最短路徑時DFS 和 BFS 的框架照樣適用。說白了二叉樹只是練習(xí) DFS/BFS 最好的“試驗田”因為它的遞歸結(jié)構(gòu)足夠簡單不會讓初學(xué)者在復(fù)雜圖結(jié)構(gòu)上迷失。7.2 后續(xù)擴(kuò)展從這五道題出發(fā)能通向哪里二叉樹的題目在 LeetCode 上是絕對的大類。刷完這五道題你可以按這個路徑繼續(xù)擴(kuò)展路徑和系列從根到葉的路徑和、路徑總和 III用 DFS 的本質(zhì)去解決。構(gòu)造二叉樹從前序與中序遍歷序列構(gòu)造二叉樹、從中序與后序遍歷序列構(gòu)造二叉樹正好用上你剛學(xué)的遍歷知識。二叉搜索樹BST 的中序遍歷結(jié)果是升序序列這個性質(zhì)能解大量 BST 題目。最近公共祖先遞歸在后序位置做判斷是后續(xù)遍歷的經(jīng)典應(yīng)用。Morris 遍歷如果不滿足于 O(h) 空間可以把空間復(fù)雜度壓到 O(1)面試進(jìn)階話題。另外我多說一句實際工程里二叉樹的遍歷也常常出現(xiàn)。比如 JSON 的樹形結(jié)構(gòu)處理、文件目錄的遞歸遍歷、搜索引擎索引樹的遍歷、表達(dá)式樹的計算底層思路都和這五道題相通。嵌入式方向的朋友如果接觸過 AVL 樹、紅黑樹也會發(fā)現(xiàn)它們的插入、刪除操作里大量用到遍歷的思路。所以說這五道題看似刷的是“算法基礎(chǔ)題”實際上是在打工程能力的地基。最后分享一個我自己的習(xí)慣遇到二叉樹題目我先不寫代碼先在白板上畫一棵三層的小樹把遍歷序列手寫出來再對著序列寫代碼。這樣代碼寫完測試用例已經(jīng)在腦子里跑過一遍了提交通過率會高很多。這個習(xí)慣幫我省了大量反復(fù)調(diào)試的時間也推薦你試試。 二叉樹遍歷五題串講：前中后序、層序與最小深度，遞歸迭代全掌握
1. 先把五行代碼的“血緣關(guān)系”理清楚刷LeetCode的朋友應(yīng)該都有過這樣一種體驗今天刷了144題前序遍歷AC了感覺很簡單明天做94題中序遍歷也AC了覺得不過如此后天碰到145題后序遍歷順手就寫完了——然后第102題層序遍歷直接懵了第111題最小深度又開始懷疑自己到底懂不懂二叉樹。這五道題放在一起刷其實挺有講究的。它們恰好覆蓋了二叉樹最核心的幾種遍歷方式前序、中序、后序?qū)儆谏疃葍?yōu)先搜索DFS的范疇層序?qū)儆趶V度優(yōu)先搜索BFS的范疇而最小深度這道題表面上考查的是樹的深度計算實際上把DFS和BFS兩條路線都串起來了?？梢哉f二叉樹遍歷的遞歸模板、迭代棧寫法、隊列層序遍歷技巧以及邊界條件判斷全都濃縮在這五道題里。這篇文章我從頭到尾把這五道題串一遍不講虛的直接給代碼、給執(zhí)行過程、給踩坑點(diǎn)。不管你用的是C、Java還是Python思路是通用的。寫完之后你會發(fā)現(xiàn)二叉樹的遍歷根本不是靠背模板而是靠理解“節(jié)點(diǎn)訪問時機(jī)”和“棧/隊列的入出順序”。1.1 前序、中序、后序命名規(guī)則已經(jīng)告訴你全部信息先看最基礎(chǔ)的定義。二叉樹的前序、中序、后序遍歷三個名字里的“前”“中”“后”指的是根節(jié)點(diǎn)被訪問的位置前序遍歷根節(jié)點(diǎn) → 左子樹 → 右子樹根在前中序遍歷左子樹 → 根節(jié)點(diǎn) → 右子樹根在中間后序遍歷左子樹 → 右子樹 → 根節(jié)點(diǎn)根在后這三個順序是對“根節(jié)點(diǎn)”而言的。左子樹永遠(yuǎn)在右子樹之前這一點(diǎn)不變。所以記的時候不需要死記“前中后”只需要記住根在哪前序先輸出根再遞歸左再遞歸右。中序先遞歸左再輸出根再遞歸右。后序先遞歸左再遞歸右最后輸出根。一句話總結(jié)根的位置決定了遍歷的名字。你只要把根放到對應(yīng)位置整棵樹的輸出順序就對了。1.2 層序和最小深度從“縱向”到“橫向”的思路切換層序遍歷Level Order Traversal是另一種維度的遍歷。DFS系列是一路走到葉子再返回BFS層序遍歷則是從上到下、從左到右一層一層地掃過去。比如這樣一棵樹3 / \ 9 20 / \ 15 7前序輸出是 3, 9, 20, 15, 7層序輸出是 [3], [9, 20], [15, 7]每一層單獨(dú)成一組。這個“按層分組”的特性是第102題的關(guān)鍵。第111題最小深度屬于“二叉樹深度/高度”這類問題。套路上可以遞歸來做也可以配合層序BFS來做而且BFS在這道題上有天然的效率優(yōu)勢——因為BFS一旦碰到第一個葉子節(jié)點(diǎn)就能立刻返回當(dāng)前層數(shù)。這個優(yōu)化在面試?yán)锪钠饋砗芗臃帧?. 遞歸解法三行代碼解決前中后序遞歸是二叉樹的“母語”。因為二叉樹本身就是遞歸定義的左子樹是一棵樹右子樹也是一棵樹。所以用遞歸去遍歷二叉樹邏輯最直觀代碼也最短。2.1 遞歸三要素終止條件、遞歸調(diào)用、操作時機(jī)寫二叉樹的遞歸其實只需要記住一個模板void traverse(TreeNode* root) { // 終止條件 if (root nullptr) return; // 前序位置先訪問根 traverse(root-left); // 中序位置左子樹遍歷完訪問根 traverse(root-right); // 后序位置左右子樹都遍歷完訪問根 }你發(fā)現(xiàn)沒有前序、中序、后序的代碼結(jié)構(gòu)完全一樣區(qū)別僅僅在于“操作根節(jié)點(diǎn)”的語句放在哪個位置。放在最前面就是前序放在中間就是中序放在最后面就是后序。這就是“訪問時機(jī)”的核心意義。很多初學(xué)者寫遞歸會卡在“為什么這個遞歸過程和我手動模擬的不一樣”。原因在于遞歸是借助系統(tǒng)調(diào)用棧完成的。你調(diào)用 traverse(root-left) 的時候當(dāng)前函數(shù)的狀態(tài)會被壓棧保存等左子樹全部執(zhí)行完棧頂彈出回到當(dāng)前節(jié)點(diǎn)繼續(xù)往下走。理解這一點(diǎn)后面看迭代法就輕松了。2.2 完整代碼實現(xiàn)與執(zhí)行軌跡第144題前序遍歷C寫法void preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); // 前序先訪問根 preorder(root-left, res); // 再左 preorder(root-right, res); // 后右 } vectorint preorderTraversal(TreeNode* root) { vectorint res; preorder(root, res); return res; }第94題中序遍歷void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); // 先左 res.push_back(root-val); // 中序再訪問根 inorder(root-right, res); // 后右 } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; }第145題后序遍歷void postorder(TreeNode* root, vectorint res) { if (!root) return; postorder(root-left, res); // 先左 postorder(root-right, res); // 再右 res.push_back(root-val); // 后序最后訪問根 } vectorint postorderTraversal(TreeNode* root) { vectorint res; postorder(root, res); return res; }用一棵小樹手動走一遍前序遍歷root 1左子節(jié)點(diǎn) 2右子節(jié)點(diǎn) 3其中 2 沒有子節(jié)點(diǎn)3 的左子節(jié)點(diǎn) 4。1 / \ 2 3 / 4前序遍歷的執(zhí)行過程是訪問 1 → 進(jìn)入 2訪問 2→ 2 的左右為空返回 → 進(jìn)入 3訪問 3→ 進(jìn)入 4訪問 4→ 4 返回 → 3 返回 → 結(jié)束。輸出1, 2, 3, 4。中序則是進(jìn)入 2左空訪問 2→ 返回 → 訪問 1 → 進(jìn)入 3 → 進(jìn)入 4訪問 4→ 返回 → 訪問 3 → 輸出2, 1, 4, 3。后序輸出2, 4, 3, 1。2.3 遞歸解法的局限不僅棧溢出還有效率問題遞歸雖然好寫但有兩個問題。第一個是樹深度很大時系統(tǒng)?？赡芤绯?。LeetCode上雖然一般不會讓遞歸爆棧但面試官一定會問“遞歸的缺點(diǎn)是什么”提前想好這一點(diǎn)非常有價值。第二個問題是遞歸過程中有大量函數(shù)調(diào)用開銷。這個在LeetCode的測試數(shù)據(jù)里體現(xiàn)不出來但在真實業(yè)務(wù)場景中如果一棵樹有幾萬甚至幾十萬個節(jié)點(diǎn)遞歸的性能瓶頸就出來了。所以掌握迭代法是必須的這不只是面試題也是實操中構(gòu)建健壯代碼的能力。3. 迭代解法用顯式棧還原遞歸過程迭代法的思路是用一個顯式棧std::stack來模擬遞歸調(diào)用時的系統(tǒng)棧。理解了遞歸的執(zhí)行順序再來看迭代法你會發(fā)現(xiàn)整個過程就是“把遞歸調(diào)用棧手動寫出來”。3.1 前序遍歷根先出先壓右再壓左前序的順序是“根 → 左 → 右”。用棧實現(xiàn)時因為棧是后進(jìn)先出所以入棧時要先壓右子節(jié)點(diǎn)再壓左子節(jié)點(diǎn)這樣左子節(jié)點(diǎn)才會先被彈出。vectorint preorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return res; }這個思路一句話概括彈一個訪問一個把右左依次入棧。很多人寫錯的地方是入棧順序記反了就變成“根右左”了。3.2 中序遍歷一路向左彈出訪問轉(zhuǎn)右繼續(xù)中序比前序稍微復(fù)雜一點(diǎn)因為順序是“左 → 根 → 右”你不能一開始就把根彈出去訪問需要先一路向左壓棧直到左子樹為空再彈出訪問然后轉(zhuǎn)向右子樹。vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { // 一路向左壓棧 while (cur) { st.push(cur); cur cur-left; } // 彈出訪問 cur st.top(); st.pop(); res.push_back(cur-val); // 轉(zhuǎn)向右子樹 cur cur-right; } return res; }這里最關(guān)鍵的變量是cur它代表“當(dāng)前需要處理的節(jié)點(diǎn)”。第一個內(nèi)層 while 把左鏈全部壓棧然后彈出一個訪問再讓cur指向右子樹。右子樹同樣會進(jìn)入內(nèi)層 while 把它的左鏈壓棧。這個過程完整模擬了遞歸中“進(jìn)入左子樹 → 訪問根 → 進(jìn)入右子樹”的步驟。3.3 后序遍歷兩個棧的思路或者一個棧加反轉(zhuǎn)后序的順序是“左 → 右 → 根”。直接用一個棧模擬會遇到一個問題根節(jié)點(diǎn)被彈出來時還不到訪問時機(jī)因為要等右子樹處理完才能訪問。所以后序的迭代實現(xiàn)是三種遍歷里最容易出錯的。一個經(jīng)典的技巧是用類似前序的思路先得到“根 → 右 → 左”的順序然后反轉(zhuǎn)。vectorint postorderTraversal(TreeNode* root) { vectorint res; if (!root) return res; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); // 注意先壓左再壓右這樣先彈出的是右 if (node-left) st.push(node-left); if (node-right) st.push(node-right); } reverse(res.begin(), res.end()); return res; }這段代碼的邏輯是前序版本是“根 → 左 → 右”這里把壓棧順序反過來先壓左再壓右彈出的順序就變成了“根 → 右 → 左”。最后整體反轉(zhuǎn)得到“左 → 右 → 根”也就是后序。注意最后一步 reverse 是 O(n) 時間整體時間復(fù)雜度仍然是 O(n)空間復(fù)雜度 O(n)沒毛病。3.4 三種迭代對比什么時候該用哪種寫法遍歷方式核心思路入棧/處理順序易錯點(diǎn)前序彈一個訪問一個右左入棧右 → 左入棧順序?qū)懛粗行蛞宦废蜃髩簵椩L問轉(zhuǎn)右左鏈路壓棧忘記 cur cur-right后序前序變體 反轉(zhuǎn)左 → 右 入棧反轉(zhuǎn)結(jié)果壓棧順序和前序相反實際上中序和后續(xù)的迭代寫法還有更“統(tǒng)一”的版本比如給棧里壓入帶標(biāo)記的節(jié)點(diǎn)visited1表示該訪問了這里就不展開——如果面試官要求不用反轉(zhuǎn)寫出后序可以用一個prev指針記錄上一個訪問的節(jié)點(diǎn)或者用雙棧法。不過個人經(jīng)驗是后序的反轉(zhuǎn)法是最不容易寫錯的面試時優(yōu)先保證正確性。4. 第102題層序遍歷BFS隊列的標(biāo)準(zhǔn)用法層序遍歷和前中后序不是一類問題它走的是廣度優(yōu)先借用隊列一層一層往外掃。4.1 基礎(chǔ)BFS模板隊列 循環(huán)大多數(shù)人的第一版層序代碼長這樣vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; // 處理當(dāng)前層 for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }這里最關(guān)鍵的一行是int size q.size()。它必須在 for 循環(huán)之前取因為隊列在循環(huán)過程中會不斷加入下一層的節(jié)點(diǎn)q.size()會變化。提前取好sizefor 循環(huán)只處理當(dāng)前層已有的節(jié)點(diǎn)下一層的節(jié)點(diǎn)自然留在隊列里為下一輪外層循環(huán)做準(zhǔn)備。4.2 為什么要按層分組從一維輸出到二維輸出第102題要求的輸出是一個二維數(shù)組每個子數(shù)組是某一層的節(jié)點(diǎn)。所以你會看到代碼里多了一個vectorint level每一層單獨(dú)收集再 push 到結(jié)果。如果換成蛇形走位Z字形輸出只需要加一個層號判斷偶數(shù)層從左到右奇數(shù)層從右到左翻轉(zhuǎn)一下level即可。這道題還有個常見的變體是“二叉樹的右視圖”。思路也是層序只是每層只取最后一個節(jié)點(diǎn)。理解了按層分組的模板這些變體基本是半小時內(nèi)能拿下的量。4.3 層序變體一網(wǎng)打盡二叉樹的層序遍歷 II自底向上BFS 結(jié)束后 reverse 整個res。二叉樹的鋸齒形層序遍歷根據(jù)層號奇偶決定是否反轉(zhuǎn)level。二叉樹的右視圖每層取level.back()。填充每個節(jié)點(diǎn)的下一個右側(cè)節(jié)點(diǎn)指針層序遍歷時用前一個節(jié)點(diǎn)pre-next cur。這些都建立在同一個 BFS 模板上。所以第102題不只是背模板理解“當(dāng)前層節(jié)點(diǎn)數(shù)量在進(jìn)入循環(huán)前鎖定”這個思想后面的變體題都能換湯不換藥地解決。5. 第111題最小深度DFS與BFS的抉擇第111題要求返回二叉樹的最小深度這里的深度是指從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)。注意幾個關(guān)鍵字葉子節(jié)點(diǎn)、最近、節(jié)點(diǎn)數(shù)。這三者缺一不可。5.1 遞歸寫法最容易忽略的“單子樹為空”場景最小深度的遞歸直覺寫法是左子樹最小深度和右子樹最小深度取較小值再加1。對應(yīng)代碼int minDepth(TreeNode* root) { if (!root) return 0; int left minDepth(root-left); int right minDepth(root-right); return min(left, right) 1; }看起來沒問題但跑測試就會發(fā)現(xiàn)對于一個只有左子樹的節(jié)點(diǎn)上面代碼會返回 1——這是錯的。比如下面這棵樹1 / 2根節(jié)點(diǎn) 1 沒有右子樹所以right 0min(1, 0) 1 1。但根節(jié)點(diǎn) 1 不是葉子節(jié)點(diǎn)所以最小深度不可能是 1應(yīng)該是 2。原因在于當(dāng)一個節(jié)點(diǎn)只有左子樹或只有右子樹時空的那一側(cè)不能參與最小深度比較。正確寫法int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left) return minDepth(root-right) 1; if (!root-right) return minDepth(root-left) 1; return min(minDepth(root-left), minDepth(root-right)) 1; }這算是題意理解的一個小坑但實際面試中問“最小深度”十有八九會碰到這個陷阱。關(guān)鍵判斷依據(jù)是空節(jié)點(diǎn)不算葉子所以不存在“空子樹深度為0參與比較”這回事。5.2 BFS解法找到第一個葉子節(jié)點(diǎn)就返回BFS 解法與上述 DFS 的遞歸寫法思路不同層序遍歷從上到下掃當(dāng)碰到第一個“左右子節(jié)點(diǎn)都為空”的節(jié)點(diǎn)時當(dāng)前層數(shù)就是最小深度。由于 BFS 是一層一層掃的第一次遇到葉子節(jié)點(diǎn)一定是在最小深度那一層。int minDepth(TreeNode* root) { if (!root) return 0; queuepairTreeNode*, int q; q.push({root, 1}); while (!q.empty()) { auto [node, depth] q.front(); q.pop(); if (!node-left !node-right) return depth; if (node-left) q.push({node-left, depth 1}); if (node-right) q.push({node-right, depth 1}); } return 0; }也可以沿用層序模板用level記錄當(dāng)前層數(shù)。BFS 的優(yōu)點(diǎn)在這個問題里非常明顯一旦找到葉子節(jié)點(diǎn)就立刻返回不需要遍歷整棵樹。對于一棵很“偏”的樹最壞情況是 BFS 退化成遍歷整棵樹復(fù)雜度仍是 O(n)但平均情況下 BFS 往往比 DFS 更早返回。5.3 最大深度 vs 最小深度一個容易混淆的點(diǎn)最大深度用 DFS 遞歸寫起來就簡單得多不會有人寫錯max(left, right) 1。最大和最小的區(qū)別在于最大深度可以用空子樹返回 0 來參與比較因為max(0, 1) 1不影響正確性最小深度則不行因為min(0, 1) 0會直接吞掉另一側(cè)的實際深度。理解了這個邏輯你就能從“背題”升級到“懂題”。6. 實戰(zhàn)中的邊界條件與常見坑位五道題刷一遍容易但會犯的錯基本都集中在邊界條件上。這里我按踩坑頻率從高到低列一遍都是真實刷題和面試中見過的問題。6.1 空樹任何遍歷的第一步都是判空幾乎每一道二叉樹題目的遞歸版本開頭都是if (!root) return ...。迭代版本則要在開始時就判斷if (!root) return ...否則訪問root-val直接空指針異常。尤其是在層序和最小深度題里空樹返回的應(yīng)該是空數(shù)組或 0千萬別把空指針推進(jìn)隊列。6.2 隊列和棧里存的是什么節(jié)點(diǎn)本身還是包裝對象層序遍歷 BFS 的隊列queueTreeNode*存的是節(jié)點(diǎn)指針第111題的最小深度 BFS 版本存的是pairTreeNode*, int用來同時記錄節(jié)點(diǎn)和層數(shù)。有些同學(xué)圖省事只存int depth那你就丟失了節(jié)點(diǎn)信息根本沒法繼續(xù)遍歷。分清容器里存的東西是你代碼能否跑通的關(guān)鍵。實際上還有一種更巧的寫法是每層用一個for循環(huán)depth在外層循環(huán)中加1隊列只存節(jié)點(diǎn)。這種寫法在代碼上更統(tǒng)一。6.3 遞歸和迭代的時間/空間復(fù)雜度解法時間復(fù)雜度空間復(fù)雜度遞歸調(diào)用棧/棧/隊列遞歸 DFSO(n)O(h)h 為樹高迭代 DFSO(n)O(h)層序 BFSO(n)O(n)最壞情況是一層能放 n/2 個節(jié)點(diǎn)在 LeetCode 的題解討論區(qū)很多人只關(guān)注時間復(fù)雜度是 O(n)但空間復(fù)雜度的分析一樣是面試必問。遞歸的空間復(fù)雜度是調(diào)用棧的深度也就是樹的高度如果樹退化成鏈表h n就會 O(n) 空間。6.4 調(diào)試技巧如何用一個小輸入驗證代碼二叉樹的題目調(diào)試有一個非常高效的方法用最小測試用例逐步走查。比如用一個只有根節(jié)點(diǎn)的樹、一個只有左子樹的樹、一個空樹分別跑一遍前中后序、層序、最小深度。這三個用例能擋住 90% 的邊界錯誤。另外寫代碼前先自己在紙上把樹畫出來標(biāo)出預(yù)期遍歷順序再跑代碼對照。我見過太多同學(xué)上來就刷題連前序和后序輸出到底差在哪都沒想清楚代碼寫錯了也不知道。如果面試時被要求“手動模擬一遍算法流程”畫圖 口頭模擬的能力比代碼本身更讓面試官眼前一亮。7. 從五道題到一套通用方法論五道題刷完回頭看它們其實在鍛煉同一套能力你把一棵樹抽象成一個數(shù)據(jù)流然后用某種方式把數(shù)據(jù)流里的元素拿出來。7.1 判空、遞歸、棧模擬、隊列模擬套路萬變不離其宗遞歸解法依賴系統(tǒng)棧迭代解法依賴顯式棧。DFS前中后序的本質(zhì)是“先深入再回溯”用?；蜻f歸實現(xiàn)。BFS層序的本質(zhì)是“逐層擴(kuò)散”用隊列實現(xiàn)。最小深度的 DFS 版本要處理單子樹為空BFS 版本則找到葉子即返回。這套方法論不只能解決二叉樹題。當(dāng)你去做圖的遍歷、拓?fù)渑判?、最短路徑時DFS 和 BFS 的框架照樣適用。說白了二叉樹只是練習(xí) DFS/BFS 最好的“試驗田”因為它的遞歸結(jié)構(gòu)足夠簡單不會讓初學(xué)者在復(fù)雜圖結(jié)構(gòu)上迷失。7.2 后續(xù)擴(kuò)展從這五道題出發(fā)能通向哪里二叉樹的題目在 LeetCode 上是絕對的大類。刷完這五道題你可以按這個路徑繼續(xù)擴(kuò)展路徑和系列從根到葉的路徑和、路徑總和 III用 DFS 的本質(zhì)去解決。構(gòu)造二叉樹從前序與中序遍歷序列構(gòu)造二叉樹、從中序與后序遍歷序列構(gòu)造二叉樹正好用上你剛學(xué)的遍歷知識。二叉搜索樹BST 的中序遍歷結(jié)果是升序序列這個性質(zhì)能解大量 BST 題目。最近公共祖先遞歸在后序位置做判斷是后續(xù)遍歷的經(jīng)典應(yīng)用。Morris 遍歷如果不滿足于 O(h) 空間可以把空間復(fù)雜度壓到 O(1)面試進(jìn)階話題。另外我多說一句實際工程里二叉樹的遍歷也常常出現(xiàn)。比如 JSON 的樹形結(jié)構(gòu)處理、文件目錄的遞歸遍歷、搜索引擎索引樹的遍歷、表達(dá)式樹的計算底層思路都和這五道題相通。嵌入式方向的朋友如果接觸過 AVL 樹、紅黑樹也會發(fā)現(xiàn)它們的插入、刪除操作里大量用到遍歷的思路。所以說這五道題看似刷的是“算法基礎(chǔ)題”實際上是在打工程能力的地基。最后分享一個我自己的習(xí)慣遇到二叉樹題目我先不寫代碼先在白板上畫一棵三層的小樹把遍歷序列手寫出來再對著序列寫代碼。這樣代碼寫完測試用例已經(jīng)在腦子里跑過一遍了提交通過率會高很多。這個習(xí)慣幫我省了大量反復(fù)調(diào)試的時間也推薦你試試。