現(xiàn))
考 408 的同學(xué)大概率都有過這種體驗(yàn)一道選擇題四個(gè)選項(xiàng)看起來都對(duì)或者看起來都錯(cuò)最后蒙了一個(gè)答案還真的就是那個(gè)“看起來最像答案”的。2011 年統(tǒng)考數(shù)據(jù)結(jié)構(gòu)第 5 題就是這種題。題干很簡(jiǎn)短——給出二叉樹的先序遍歷序列要求判斷哪個(gè)中序遍歷序列不可能出現(xiàn)。很多人第一次做這道題時(shí)會(huì)很困惑先序和中序不是能唯一確定一棵二叉樹嗎那為什么還會(huì)出現(xiàn)“不可能”的選項(xiàng)難道任意給出一個(gè)中序序列都能構(gòu)造出一棵滿足先序的樹這里先給出一個(gè)明確判斷這道題的核心不是“背遍歷規(guī)則”而是“理解遍歷序列之間的約束關(guān)系”。先序序列確定根中序序列確定左右子樹的劃分兩者放在一起本質(zhì)上是對(duì)一棵二叉樹做“雙重描述”。如果兩個(gè)序列互相矛盾就無法還原出任何一棵樹。2011 年第 5 題考的就是這個(gè)矛盾的檢測(cè)能力。讀完這篇文章你會(huì)得到三樣?xùn)|西第一一個(gè) 30 秒內(nèi)手算排除錯(cuò)誤選項(xiàng)的三步法第二一份可以直接運(yùn)行的 C/Python 代碼用來判斷任意“先序中序”組合是否合法第三在合法前提下重建二叉樹、輸出后序序列的完整實(shí)現(xiàn)。這套能力不僅對(duì)這道真題有效對(duì)以后遇到“后序中序求先序”“層次中序恢復(fù)二叉樹”這一類題同樣適用。1. 2011年第5題到底在考什么這道題出現(xiàn)在 2011 年 408 統(tǒng)考數(shù)據(jù)結(jié)構(gòu)部分題目本身并不長(zhǎng)但錯(cuò)誤率一直不低。原因是很多同學(xué)對(duì)二叉樹遍歷的理解停留在“能寫出遞歸代碼”這個(gè)層面卻沒有理解一個(gè)更根本的問題當(dāng)兩個(gè)遍歷序列同時(shí)給出時(shí)它們之間有哪些必須滿足的約束先回顧一下三種遍歷的定義。先序遍歷的順序是“根、左、右”中序遍歷的順序是“左、根、右”后序遍歷的順序是“左、右、根”。注意這里的“根”指的是當(dāng)前子樹的根不是整棵樹的根。對(duì)于一棵樹中的任意一個(gè)子樹這三個(gè)順序都成立。遍歷方式訪問順序核心作用先序遍歷根、左、右第一個(gè)元素必為整棵樹的根中序遍歷左、根、右根的位置把左右子樹結(jié)點(diǎn)分開后序遍歷左、右、根最后一個(gè)元素必為整棵樹的根層次遍歷從上到下、從左到右可配合中序恢復(fù)二叉樹2011 年第 5 題的考法就是給定先序序列讓考生在四個(gè)中序序列中找出“不可能”的那個(gè)。為什么會(huì)有“不可能”因?yàn)橄刃蛐蛄邢薅烁奈恢枚行蛐蛄邢薅俗笥易訕涞慕Y(jié)點(diǎn)集合兩者一旦沖突就沒有任何一棵二叉樹能同時(shí)滿足這兩個(gè)序列。從 408 的命題風(fēng)格來看這道題真正想考查的是“根據(jù)兩種遍歷序列恢復(fù)二叉樹”的逆向能力。先序中序可以唯一確定一棵二叉樹這是教材結(jié)論但這個(gè)結(jié)論成立的前提是“兩個(gè)序列來自同一棵樹”。題目就是把這個(gè)前提拿掉讓學(xué)生判斷“給定的兩個(gè)序列是否真的來自同一棵樹”。換句話說它把正向的“給樹求序列”變成了逆向的“給序列驗(yàn)樹”。這里要特別強(qiáng)調(diào)一個(gè)判斷刷這道題時(shí)如果只記住某個(gè)選項(xiàng)是答案那這道題就白刷了。因?yàn)?408 對(duì)遍歷序列的考查方式一直在變化但核心邏輯不變。真正要掌握的是“先序定根、中序分割、遞歸驗(yàn)證”這套通用方法。掌握了它不管選項(xiàng)怎么變你都能在幾十秒內(nèi)完成判斷。2. 核心原理先序中序?yàn)槭裁茨芪ㄒ淮_定一棵二叉樹要理解“哪個(gè)中序不可能”首先要理解“先序中序?yàn)槭裁茨艽_定一棵二叉樹”。這兩個(gè)序列之間的關(guān)系可以用三個(gè)關(guān)鍵觀察來概括。第一個(gè)觀察先序序列的第一個(gè)元素一定是整棵樹的根結(jié)點(diǎn)。因?yàn)橄刃虮闅v最先訪問的就是根這是定義沒有任何例外。第二個(gè)觀察得到根結(jié)點(diǎn)之后去中序序列里找到這個(gè)根根左邊的所有結(jié)點(diǎn)一定屬于左子樹根右邊的所有結(jié)點(diǎn)一定屬于右子樹。中序遍歷的順序是“左、根、右”所以根天然地把結(jié)點(diǎn)分成左右兩個(gè)部分。第三個(gè)觀察也是最重要的左子樹和右子樹的結(jié)點(diǎn)在先序序列中也必須是連續(xù)的兩段。先序遍歷的順序是“根、左、右”根訪問完之后緊接著訪問整棵左子樹左子樹訪問完才訪問右子樹。因此如果中序序列告訴我們左子樹有 L 個(gè)結(jié)點(diǎn)那么先序序列中緊隨根之后的 L 個(gè)結(jié)點(diǎn)必須全部屬于左子樹集合再往后的結(jié)點(diǎn)必須全部屬于右子樹集合。這三個(gè)觀察合在一起就構(gòu)成了“先序中序唯一確定二叉樹”的證明過程同時(shí)也是判斷“序列是否合法”的判定規(guī)則。用一個(gè)小例子演示這個(gè)過程。假設(shè)先序序列是 ABDCE中序序列是 DBAEC。先取先序第一個(gè)元素 A 作為根在中序 DBAEC 中找到 A位置在中間偏右。A 左邊是 DB說明左子樹集合是 {D, B}A 右邊是 EC說明右子樹集合是 {E, C}。再看先序序列 ABDCE。根 A 之后是 B、D、C、E 這 4 個(gè)結(jié)點(diǎn)。左子樹有 2 個(gè)結(jié)點(diǎn)所以先序中 A 之后的 2 個(gè)結(jié)點(diǎn) B、D 必須屬于左子樹集合確實(shí) {B, D} {D, B}。剩下 C、E 屬于右子樹集合確實(shí) {C, E} {E, C}。第一層驗(yàn)證通過。接下來遞歸驗(yàn)證左子樹。左子樹的先序片段是 BD中序片段是 DB。根是 B中序中 B 的左邊是 D說明左子樹的左子樹是 {D}右子樹為空。再看左子樹先序 BD根 B 之后是 D正好屬于左子樹集合。驗(yàn)證通過。右子樹同理先序 CE中序 EC根 C左子樹 E驗(yàn)證通過。因此這兩個(gè)序列確實(shí)來自同一棵樹。這里的關(guān)鍵在于每一次分割后都要用“左子樹結(jié)點(diǎn)數(shù)”去切割先序序列。左子樹有多少個(gè)結(jié)點(diǎn)根后面的前多少個(gè)位置就必須是左子樹的先序片段。這就是“約束”二字的真正含義。如果某個(gè)中序序列給出的左子樹集合和先序序列中緊隨根后的結(jié)點(diǎn)集合對(duì)不上那就說明這個(gè)中序序列不可能是該先序序列對(duì)應(yīng)的任何一棵二叉樹的中序序列。這就是 2011 年第 5 題所有“不可能”選項(xiàng)的根源。3. 手算解法30秒排除不可能的“三步法”選擇題不需要真的把整棵樹完整還原。絕大多數(shù)選項(xiàng)在第一層驗(yàn)證時(shí)就能排除。這里給出一個(gè)適合考場(chǎng)上使用的手算三步法。3.1 三步法總覽第一步確定根。先序序列的第一個(gè)元素就是當(dāng)前子樹的根。第二步在中序序列中找到根的位置。根左邊有多少個(gè)結(jié)點(diǎn)就說明左子樹有多少個(gè)結(jié)點(diǎn)根右邊有多少個(gè)結(jié)點(diǎn)就說明右子樹有多少個(gè)結(jié)點(diǎn)。第三步用左子樹結(jié)點(diǎn)數(shù)去切割先序序列。先序序列中根后面的前 L 個(gè)結(jié)點(diǎn)必須全部來自中序中根左邊的集合后 n-L-1 個(gè)結(jié)點(diǎn)必須全部來自中序中根右邊的集合。如果匹配對(duì)左子樹和右子樹繼續(xù)遞歸驗(yàn)證如果不匹配直接判定不可能。這個(gè)方法的本質(zhì)就是把“先序中序唯一確定二叉樹”的證明過程反著用。每一層只需要做一件事檢查“先序中緊跟根的那一段”和“中序中根左右兩段”是否集合一致。3.2 手算實(shí)例先序 ABCDEF中序 CABDEF用先序 ABCDEF 和中序 CABDEF 走一遍完整流程。先序第一個(gè)元素是 AA 就是整棵樹的根。在中序 CABDEF 中找到 A位置在第 2 個(gè)下標(biāo)從 1 開始。A 的左邊只有一個(gè)結(jié)點(diǎn) C說明左子樹集合是 {C}左子樹大小為 1。A 的右邊是 B、D、E、F說明右子樹集合是 {B, D, E, F}?，F(xiàn)在用左子樹大小 1 去切割先序。先序是 A、B、C、D、E、F根 A 之后應(yīng)該是 1 個(gè)左子樹結(jié)點(diǎn)也就是 B?？墒?B 并不在左子樹集合 {C} 中而是屬于右子樹集合。這就矛盾了如果 B 是 A 的左孩子它應(yīng)該出現(xiàn)在中序 A 的左邊但中序 A 的左邊只有 C如果 B 不是左孩子那左子樹大小就不是 1而先序中 A 后緊接著就是 B這與“先序先遍歷左子樹”矛盾。所以 CABDEF 不可能成為先序 ABCDEF 對(duì)應(yīng)二叉樹的中序序列。整個(gè)過程只需要十幾秒不需要畫樹。3.3 容易忽略的遞歸驗(yàn)證三步法中第三步看起來只是集合判斷但要注意集合判斷只是必要條件不是充分條件。第一層通過后左右子樹內(nèi)部仍然可能存在矛盾。舉例來說先序 ABCDEF中序 CBADEF。第一層檢查根 A中序中 A 左邊是 CB左子樹集合 {C, B}左子樹大小 2先序 A 后是 B、C恰好都屬于左子樹集合右邊 D、E、F 都屬于右子樹集合。第一層通過。但如果就此判定合法是不夠嚴(yán)謹(jǐn)?shù)摹＿€要繼續(xù)看左子樹左子樹先序片段是 BC中序片段是 CB。根 B中序中 B 的左邊是 C左子樹集合 {C}左子樹大小 1再看先序 BC根 B 后是 CC 確實(shí)在左子樹集合中驗(yàn)證通過。右子樹先序 DEF中序 DEF根 D右子樹 EF同樣通過。因此 CBADEF 確實(shí)合法。在選擇題里出題人經(jīng)常會(huì)把干擾項(xiàng)設(shè)計(jì)成“第一層看起來沒問題但子樹內(nèi)部有問題”的形式。所以手算時(shí)至少要做到第二層、第三層的遞歸驗(yàn)證不能只驗(yàn)證根這一層就下結(jié)論。4. 完整示例先序 ABCDEF 的四種中序誰不可能下面用一組典型的選項(xiàng)設(shè)計(jì)來演示完整判斷過程。給定先序序列 ABCDEF有四個(gè)中序序列候選A. A B C D E FB. B A C D E FC. C B A D E FD. C A B D E F用三步法逐個(gè)驗(yàn)證。先看選項(xiàng) A中序 ABCDEF。根是 A中序中 A 在最左邊說明左子樹為空右子樹結(jié)點(diǎn)集合是 {B, C, D, E, F}。先序中 A 后面的 B C D E F 全部屬于右子樹集合長(zhǎng)度也正確。進(jìn)一步檢查右子樹先序 BCDEF中序 BCDEF根 B同樣結(jié)構(gòu)。這說明整棵樹是一條只向右延伸的鏈A 的右孩子是 BB 的右孩子是 C以此類推。選項(xiàng) A 合法。再看選項(xiàng) B中序 BACDEF。根 A 在中序中位于第 2 位左邊只有 B左子樹集合 {B}右子樹集合 {C, D, E, F}。先序中 A 后第一個(gè)是 B確實(shí)屬于左子樹集合且左子樹大小為 1剩下的 C D E F 屬于右子樹集合。驗(yàn)證通過。對(duì)應(yīng)樹的結(jié)構(gòu)是A 的左孩子是 BA 的右子樹是 C-D-E-F 這條右鏈。選項(xiàng) B 合法。接著看選項(xiàng) C中序 CBADEF。根 A 左邊是 CB左子樹集合 {C, B}大小為 2右邊是 DEF右子樹集合 {D, E, F}。先序中 A 后是 B、C這兩個(gè)正好屬于左子樹集合長(zhǎng)度 2后面的 D、E、F 屬于右子樹集合。第一層通過。再看左子樹先序 BC中序 CB根 B左子樹為 C可以匹配。選項(xiàng) C 合法。最后看選項(xiàng) D中序 CABDEF。根 A 左邊只有一個(gè) C左子樹集合是 {C}左子樹大小為 1右邊是 B、D、E、F。先序中 A 后第一個(gè)結(jié)點(diǎn)是 B但 B 并不在左子樹集合 {C} 中而是屬于右子樹集合。和 3.2 節(jié)的分析一樣B 的位置無法安放。因此選項(xiàng) D 是中序序列不可能出現(xiàn)的情況。這道題選 D。選項(xiàng) D 是很好的干擾項(xiàng)因?yàn)樗雌饋怼昂苡兄行虻母杏X”A 在中間左右各有一堆結(jié)點(diǎn)。但正是這種表面上的“合理”讓人忽略了先序和中序之間的連續(xù)段約束。再換一個(gè)角度理解如果把先序序列看成入棧順序把中序序列看成出棧順序那么 CABDEF 這個(gè)出棧順序在棧模擬中會(huì)在第二個(gè)位置卡住。A 入棧后B 入棧此時(shí) B 壓在 A 上面如果第一個(gè)出棧的是 C那么必須先把 A、B 都?jí)哼M(jìn)去C 出棧后棧頂是 B但中序第二個(gè)元素是 A而 A 被 B 壓住無法立即出棧。矛盾由此產(chǎn)生。這個(gè)棧的視角非常重要后面寫代碼時(shí)最簡(jiǎn)潔的合法性判斷就是基于這個(gè)思路實(shí)現(xiàn)的。5. 代碼實(shí)現(xiàn)用棧模擬判斷中序序列是否合法選擇題用手算三步法已經(jīng)足夠。但如果想徹底檢驗(yàn)自己的理解或者為復(fù)試機(jī)試做準(zhǔn)備就應(yīng)該把判斷邏輯寫成代碼。5.1 算法思路先序是入棧序中序是出棧序非遞歸中序遍歷二叉樹時(shí)會(huì)用到棧。中序遍歷的訪問順序正好對(duì)應(yīng)著一種“按先序入棧、按中序出?！钡哪M過程先序序列決定結(jié)點(diǎn)什么時(shí)候入棧中序序列決定結(jié)點(diǎn)什么時(shí)候出棧。算法過程如下維護(hù)一個(gè)棧初始為空。用指針 i 指向先序序列表示下一個(gè)待入棧的結(jié)點(diǎn)。從左到右掃描中序序列的每個(gè)字符 c當(dāng)棧為空或者棧頂元素不等于 c 時(shí)不斷從先序序列中取元素入棧直到棧頂元素等于 c或者先序序列已經(jīng)全部入棧。如果先序序列已經(jīng)用盡棧頂仍然不等于 c說明這個(gè)中序序列不可能出現(xiàn)返回 false。如果棧頂?shù)扔?c彈出棧頂繼續(xù)處理中序下一個(gè)字符。如果中序序列掃描完說明所有字符都正確匹配返回 true。每個(gè)字符最多入棧一次、出棧一次所以時(shí)間復(fù)雜度是 O(n)其中 n 是序列長(zhǎng)度。5.2 C 語言完整實(shí)現(xiàn)#include stdio.h #include string.h #include stdbool.h #define MAXN 100 // 判斷中序序列 in 是否可能是先序序列 pre 對(duì)應(yīng)二叉樹的中序遍歷 bool isValidInorder(const char *pre, const char *in, int n) { char stack[MAXN]; int top -1; int i 0; // pre 序列的指針 for (int j 0; j n; j) { // ?？栈驐ｍ敳坏扔诋?dāng)前中序字符時(shí)繼續(xù)入棧 while (top -1 || stack[top] ! in[j]) { if (i n) { return false; // 先序元素全部入棧仍無法匹配 } stack[top] pre[i]; } // 匹配成功出棧 top--; } return true; } int main() { char pre[MAXN], in[MAXN]; printf(請(qǐng)輸入先序遍歷序列: ); scanf(%s, pre); printf(請(qǐng)輸入中序遍歷序列: ); scanf(%s, in); int n strlen(pre); if (strlen(in) ! n) { printf(兩個(gè)序列長(zhǎng)度不一致輸入錯(cuò)誤\n); return 0; } if (isValidInorder(pre, in, n)) { printf(該中序序列合法對(duì)應(yīng)二叉樹存在\n); } else { printf(該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生\n); } return 0; }核心邏輯集中在isValidInorder中。stack[top] pre[i]這一步把先序序列中的元素依次壓棧直到棧頂能匹配當(dāng)前要處理的中序字符。如果先序序列已經(jīng)全部壓入棧中還沒有匹配成功說明棧里剩余元素的順序和中序序列沖突該中序序列不合法。編譯和運(yùn)行命令如下gcc btree_inorder_check.c -o btree_inorder_check ./btree_inorder_check輸入一組合法序列例如先序 ABCDEF、中序 CBADEF程序輸出請(qǐng)輸入先序遍歷序列: ABCDEF 請(qǐng)輸入中序遍歷序列: CBADEF 該中序序列合法對(duì)應(yīng)二叉樹存在輸入一組非法序列例如先序 ABCDEF、中序 CABDEF程序輸出請(qǐng)輸入先序遍歷序列: ABCDEF 請(qǐng)輸入中序遍歷序列: CABDEF 該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生5.3 Python 精簡(jiǎn)版如果平時(shí)用 Python 刷題可以用下面這個(gè)更精簡(jiǎn)的版本def is_valid_inorder(pre: str, in_order: str) - bool: stack [] i 0 for ch in in_order: while not stack or stack[-1] ! ch: if i len(pre): return False stack.append(pre[i]) i 1 stack.pop() return True if __name__ __main__: pre input(請(qǐng)輸入先序遍歷序列: ).strip() in_order input(請(qǐng)輸入中序遍歷序列: ).strip() if len(pre) ! len(in_order): print(兩個(gè)序列長(zhǎng)度不一致) elif is_valid_inorder(pre, in_order): print(該中序序列合法對(duì)應(yīng)二叉樹存在) else: print(該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生)Python 版本的邏輯和 C 版本完全一致。這里要注意一個(gè)容易出錯(cuò)的點(diǎn)while not stack or stack[-1] ! ch這個(gè)條件中必須先判斷棧是否為空再判斷棧頂順序不能寫反否則空棧訪問stack[-1]會(huì)報(bào) IndexError。機(jī)試時(shí)這個(gè)棧模擬函數(shù)可以作為判斷“遍歷序列是否配對(duì)”的通用工具也可以進(jìn)一步用于重建二叉樹。6. 進(jìn)階合法時(shí)重建二叉樹并驗(yàn)證后序判斷合法性只是第一步。408 的大題和復(fù)試機(jī)試?yán)锝?jīng)常要求“給定先序和中序重建二叉樹并輸出后序”。這個(gè)需求可以在合法性的基礎(chǔ)上直接擴(kuò)展。6.1 遞歸重建的核心邏輯構(gòu)建過程和前面手算三步法一模一樣先序片段的第一個(gè)元素是根。在中序片段中找到根的位置 pos。中序片段中pos 左邊是左子樹中序pos 右邊是右子樹中序。左子樹結(jié)點(diǎn)數(shù) leftLen pos - inL用它把先序片段切成三部分根、左子樹先序、右子樹先序。遞歸構(gòu)建左右子樹。邊界條件很簡(jiǎn)單當(dāng)先序片段的左邊界大于等于右邊界時(shí)說明沒有結(jié)點(diǎn)返回 NULL。6.2 C 語言重建并輸出后序完整代碼#include stdio.h #include stdlib.h #include string.h #include stdbool.h #define MAXN 100 typedef struct TreeNode { char val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 判斷中序序列是否可能 bool isValidInorder(const char *pre, const char *in, int n) { char stack[MAXN]; int top -1; int i 0; for (int j 0; j n; j) { while (top -1 || stack[top] ! in[j]) { if (i n) return false; stack[top] pre[i]; } top--; } return true; } // 根據(jù)先序和中序重建二叉樹 TreeNode *buildTree(const char *pre, int preL, int preR, const char *in, int inL, int inR) { if (preL preR) { return NULL; } TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-val pre[preL]; // 在中序片段中查找根的位置 int pos inL; while (pos inR in[pos] ! pre[preL]) { pos; } int leftLen pos - inL; // 左子樹結(jié)點(diǎn)數(shù) // 左子樹先序 [preL1, preL1leftLen)中序 [inL, pos) node-left buildTree(pre, preL 1, preL 1 leftLen, in, inL, pos); // 右子樹先序 [preL1leftLen, preR)中序 [pos1, inR) node-right buildTree(pre, preL 1 leftLen, preR, in, pos 1, inR); return node; } void postorder(TreeNode *root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%c, root-val); } int main() { char pre[MAXN], in[MAXN]; printf(請(qǐng)輸入先序遍歷序列: ); scanf(%s, pre); printf(請(qǐng)輸入中序遍歷序列: ); scanf(%s, in); int n strlen(pre); if (strlen(in) ! n) { printf(兩個(gè)序列長(zhǎng)度不一致輸入錯(cuò)誤\n); return 0; } if (!isValidInorder(pre, in, n)) { printf(該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生\n); } else { printf(該中序序列合法\n); TreeNode *root buildTree(pre, 0, n, in, 0, n); printf(重建成功后序遍歷序列為: ); postorder(root); printf(\n); } return 0; }這段代碼把“判斷”和“重建”放在了一起。運(yùn)行示例請(qǐng)輸入先序遍歷序列: ABCDEF 請(qǐng)輸入中序遍歷序列: CBADEF 該中序序列合法 重建成功后序遍歷序列為: CBFEDA可以用前面的手算過程驗(yàn)證這個(gè)后序結(jié)果。先序 ABCDEF、中序 CBADEF 對(duì)應(yīng)這棵樹A 是根。左子樹先序 BC中序 CB根 B左孩子 C。右子樹先序 DEF中序 DEF根 D右孩子 EE 的右孩子 F。后序遍歷順序是“左、右、根”C左子樹最左葉子、B左子樹根、F右子樹最右葉子、E、D、A也就是 CBFEDA。和程序輸出一致。如果 n 很大遞歸中用循環(huán)找根的位置是 O(n) 的整體會(huì)退化到 O(n^2)。面試或機(jī)試中更穩(wěn)妥的做法是先用哈希表記錄中序序列中每個(gè)字符的下標(biāo)把查找根的位置優(yōu)化到 O(1)。哈希優(yōu)化版本需要注意一個(gè)前提二叉樹中所有結(jié)點(diǎn)值互不相同。如果存在重復(fù)值哈希表會(huì)丟失信息這也是 408 題目默認(rèn)的前提條件。7. 常見錯(cuò)誤與排查思路代碼和手算都容易踩坑。下面把出現(xiàn)頻率較高的幾個(gè)問題整理出來。問題現(xiàn)象可能原因排查方式解決方案手算認(rèn)為合法程序判斷非法兩個(gè)序列的參數(shù)順序傳反或輸入時(shí)有空格打印 pre 和 in確認(rèn)誰是誰統(tǒng)一按“先序在前、中序在后”調(diào)用元素集合相同但長(zhǎng)度一致仍判斷非法序列中存在重復(fù)字符逐字符檢查重復(fù)值會(huì)導(dǎo)致棧模擬歧義408 默認(rèn)結(jié)點(diǎn)值互異如果確實(shí)重復(fù)需要帶編號(hào)處理遞歸重建時(shí)棧溢出二叉樹退化成一條鏈遞歸深度等于結(jié)點(diǎn)數(shù)輸出樹高或檢查輸入序列是否來自極端樹形機(jī)試可改用迭代棧模擬筆試直接說明遞歸思路只驗(yàn)證根一層就下結(jié)論左子樹或右子樹內(nèi)部仍然存在矛盾對(duì)左右子樹遞歸執(zhí)行三步法至少遞歸到第二層必要時(shí)畫樹驗(yàn)證哈希優(yōu)化后結(jié)果錯(cuò)誤中序存在重復(fù)字符哈希表覆蓋了位置信息打印哈希表內(nèi)容檢查有重復(fù)值時(shí)不能直接用普通哈希表其中最常見的問題是把“集合相等”當(dāng)作“序列合法”。集合相等只是必要條件遞歸結(jié)構(gòu)也必須一致。比如先序 ABC、中序 CAB根 A 左邊是 C右邊是 B左子樹集合 {C}但先序中 A 后第一個(gè)是 BB 不在左子樹集合中所以非法。這里的矛盾發(fā)生在第一層很容易看出來。但有些題目會(huì)把矛盾藏在子樹內(nèi)部第一層集合完全匹配到第二層才暴露。做題時(shí)如果遇到兩個(gè)選項(xiàng)第一層都通過必須繼續(xù)往下驗(yàn)證子樹這就是遞歸思想的實(shí)際應(yīng)用。另一個(gè)高發(fā)問題是遞歸重建時(shí)邊界寫錯(cuò)。buildTree函數(shù)里左子樹的先序范圍是[preL1, preL1leftLen)右子樹的范圍是[preL1leftLen, preR)。很多同學(xué)會(huì)把右子樹的起點(diǎn)寫成preLleftLen少加一個(gè) 1導(dǎo)致跳過根結(jié)點(diǎn)。判斷邊界時(shí)可以打印每次遞歸的參數(shù)來核對(duì)。這個(gè)錯(cuò)誤在代碼中很難一眼發(fā)現(xiàn)但一旦輸出后序結(jié)果完全錯(cuò)亂基本就是邊界問題。8. 408復(fù)習(xí)建議與擴(kuò)展考點(diǎn)2011 年第 5 題屬于“遍歷序列恢復(fù)二叉樹”這一大考點(diǎn)。這類題目在 408 中反復(fù)出現(xiàn)而且換湯不換藥。下面把這些考點(diǎn)串起來復(fù)習(xí)效率會(huì)高很多。8.1 不同序列組合能否唯一確定二叉樹給定序列能否唯一確定二叉樹說明先序 中序能先序定根中序分左右后序 中序能后序定根中序分左右層次 中序能層次序定根順序中序分左右先序 后序不能單孩子結(jié)點(diǎn)的左右方向無法區(qū)分先序 空指針標(biāo)記能空指針標(biāo)記補(bǔ)全了左右子樹信息“先序 后序不能唯一確定”這個(gè)結(jié)論可以用最簡(jiǎn)反例說明兩個(gè)結(jié)點(diǎn)的樹根 A 的左孩子是 B和根 A 的右孩子是 B這兩種樹的先序序列都是 AB后序序列都是 BA但中序一個(gè)是 BA一個(gè)是 AB是兩棵不同的二叉樹。所以考試中只要出現(xiàn)“先序 后序還原二叉樹”的說法可以直接判斷為錯(cuò)誤或需要額外條件。8.2 與本題相似的考法第一類給后序 中序求先序。做法和先序 中序完全對(duì)稱只是要把“先序第一個(gè)元素是根”換成“后序最后一個(gè)元素是根”然后同樣用中序切割左右子樹。第二類給先序 后序問中序有多少種可能。這種題考查的是對(duì)“單孩子結(jié)點(diǎn)”的理解。每當(dāng)一個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)這個(gè)孩子在先序和后序中的相對(duì)位置體現(xiàn)不出左右對(duì)應(yīng)中序就多一種可能。第三類在二叉排序樹背景下考查遍歷。二叉排序樹的中序遍歷一定是遞增序列所以“二叉排序樹先序 中序”的組合里中序其實(shí)已經(jīng)隱含了結(jié)點(diǎn)之間的順序關(guān)系這類題通常和查找、插入結(jié)合。第四類把遍歷和棧結(jié)合。中序遍歷的非遞歸實(shí)現(xiàn)依賴棧所以“先序?yàn)槿霔ｍ樞?、中序?yàn)槌鰲ｍ樞颉边@個(gè)模型本身就是考點(diǎn)。掌握了棧模擬判斷法這類題基本是送分題。8.3 復(fù)習(xí)建議給四個(gè)可落地的建議第一先把三種遍歷的手算過關(guān)包括遞歸版本和非遞歸版本。不要只背代碼要能在紙上快速寫出任意一棵樹的先序、中序、后序。第二做“遍歷序列恢復(fù)二叉樹”的專項(xiàng)練習(xí)每天手算三題。題目不用很難重點(diǎn)是訓(xùn)練“先序定根、中序分割、左子樹長(zhǎng)度切先序”這三個(gè)動(dòng)作直到形成條件反射。第三機(jī)試必練三件事棧模擬判斷合法性、遞歸重建二叉樹、輸出另一種遍歷驗(yàn)證結(jié)果。這三個(gè)能力可以互相驗(yàn)證也是復(fù)試機(jī)試的高頻考點(diǎn)。第四錯(cuò)題本里不要只抄原題答案。把“通用解法”寫下來比如 2011 年第 5 題的通用解法就是“三步法 遞歸驗(yàn)證”下次遇到同類題直接調(diào)用這套思路而不是回憶上次選的是 A 還是 D。9. 總結(jié)與動(dòng)手練習(xí)這篇文章把 2011 年第 5 題背后的邏輯拆成了三層原理層理解先序 中序?yàn)槭裁茨芪ㄒ淮_定一棵二叉樹手算層用“三步法”快速判斷中序序列是否合法代碼層用棧模擬判斷合法性用遞歸重建二叉樹并輸出后序。其中最關(guān)鍵的一個(gè)認(rèn)知是兩個(gè)序列來自同一棵樹時(shí)先序序列中緊隨根之后的左子樹結(jié)點(diǎn)段長(zhǎng)度必須等于中序序列中根左邊結(jié)點(diǎn)的數(shù)量且這兩個(gè)集合必須一致。這個(gè)約束條件既是證明“唯一確定”的依據(jù)也是判斷“不可能”的武器。下面留三道練習(xí)題建議先手算再用代碼驗(yàn)證最后在評(píng)論區(qū)交流答案。已知先序序列為 ABCDEF中序序列為 CDBAEF這個(gè)中序序列是否合法如果合法后序序列是什么已知后序序列為 DEBFCA中序序列為 DBEAFC求先序序列。為什么“先序 后序”不能唯一確定一棵二叉樹請(qǐng)畫出一個(gè)具體反例。把 2011 年第 5 題吃透之后你會(huì)明顯感覺到408 數(shù)據(jù)結(jié)構(gòu)中對(duì)二叉樹遍歷的考查表面上是選擇題本質(zhì)上是讓你在腦子里維護(hù)一棵樹。當(dāng)你面對(duì)任意一組先序和中序序列能在幾十秒內(nèi)判斷出“這棵樹到底存不存在”時(shí)這一類題就已經(jīng)真正通了。 二叉樹遍歷序列合法性判斷：先序+中序唯一確定二叉樹的原理與實(shí)現(xiàn)
考 408 的同學(xué)大概率都有過這種體驗(yàn)一道選擇題四個(gè)選項(xiàng)看起來都對(duì)或者看起來都錯(cuò)最后蒙了一個(gè)答案還真的就是那個(gè)“看起來最像答案”的。2011 年統(tǒng)考數(shù)據(jù)結(jié)構(gòu)第 5 題就是這種題。題干很簡(jiǎn)短——給出二叉樹的先序遍歷序列要求判斷哪個(gè)中序遍歷序列不可能出現(xiàn)。很多人第一次做這道題時(shí)會(huì)很困惑先序和中序不是能唯一確定一棵二叉樹嗎那為什么還會(huì)出現(xiàn)“不可能”的選項(xiàng)難道任意給出一個(gè)中序序列都能構(gòu)造出一棵滿足先序的樹這里先給出一個(gè)明確判斷這道題的核心不是“背遍歷規(guī)則”而是“理解遍歷序列之間的約束關(guān)系”。先序序列確定根中序序列確定左右子樹的劃分兩者放在一起本質(zhì)上是對(duì)一棵二叉樹做“雙重描述”。如果兩個(gè)序列互相矛盾就無法還原出任何一棵樹。2011 年第 5 題考的就是這個(gè)矛盾的檢測(cè)能力。讀完這篇文章你會(huì)得到三樣?xùn)|西第一一個(gè) 30 秒內(nèi)手算排除錯(cuò)誤選項(xiàng)的三步法第二一份可以直接運(yùn)行的 C/Python 代碼用來判斷任意“先序中序”組合是否合法第三在合法前提下重建二叉樹、輸出后序序列的完整實(shí)現(xiàn)。這套能力不僅對(duì)這道真題有效對(duì)以后遇到“后序中序求先序”“層次中序恢復(fù)二叉樹”這一類題同樣適用。1. 2011年第5題到底在考什么這道題出現(xiàn)在 2011 年 408 統(tǒng)考數(shù)據(jù)結(jié)構(gòu)部分題目本身并不長(zhǎng)但錯(cuò)誤率一直不低。原因是很多同學(xué)對(duì)二叉樹遍歷的理解停留在“能寫出遞歸代碼”這個(gè)層面卻沒有理解一個(gè)更根本的問題當(dāng)兩個(gè)遍歷序列同時(shí)給出時(shí)它們之間有哪些必須滿足的約束先回顧一下三種遍歷的定義。先序遍歷的順序是“根、左、右”中序遍歷的順序是“左、根、右”后序遍歷的順序是“左、右、根”。注意這里的“根”指的是當(dāng)前子樹的根不是整棵樹的根。對(duì)于一棵樹中的任意一個(gè)子樹這三個(gè)順序都成立。遍歷方式訪問順序核心作用先序遍歷根、左、右第一個(gè)元素必為整棵樹的根中序遍歷左、根、右根的位置把左右子樹結(jié)點(diǎn)分開后序遍歷左、右、根最后一個(gè)元素必為整棵樹的根層次遍歷從上到下、從左到右可配合中序恢復(fù)二叉樹2011 年第 5 題的考法就是給定先序序列讓考生在四個(gè)中序序列中找出“不可能”的那個(gè)。為什么會(huì)有“不可能”因?yàn)橄刃蛐蛄邢薅烁奈恢枚行蛐蛄邢薅俗笥易訕涞慕Y(jié)點(diǎn)集合兩者一旦沖突就沒有任何一棵二叉樹能同時(shí)滿足這兩個(gè)序列。從 408 的命題風(fēng)格來看這道題真正想考查的是“根據(jù)兩種遍歷序列恢復(fù)二叉樹”的逆向能力。先序中序可以唯一確定一棵二叉樹這是教材結(jié)論但這個(gè)結(jié)論成立的前提是“兩個(gè)序列來自同一棵樹”。題目就是把這個(gè)前提拿掉讓學(xué)生判斷“給定的兩個(gè)序列是否真的來自同一棵樹”。換句話說它把正向的“給樹求序列”變成了逆向的“給序列驗(yàn)樹”。這里要特別強(qiáng)調(diào)一個(gè)判斷刷這道題時(shí)如果只記住某個(gè)選項(xiàng)是答案那這道題就白刷了。因?yàn)?408 對(duì)遍歷序列的考查方式一直在變化但核心邏輯不變。真正要掌握的是“先序定根、中序分割、遞歸驗(yàn)證”這套通用方法。掌握了它不管選項(xiàng)怎么變你都能在幾十秒內(nèi)完成判斷。2. 核心原理先序中序?yàn)槭裁茨芪ㄒ淮_定一棵二叉樹要理解“哪個(gè)中序不可能”首先要理解“先序中序?yàn)槭裁茨艽_定一棵二叉樹”。這兩個(gè)序列之間的關(guān)系可以用三個(gè)關(guān)鍵觀察來概括。第一個(gè)觀察先序序列的第一個(gè)元素一定是整棵樹的根結(jié)點(diǎn)。因?yàn)橄刃虮闅v最先訪問的就是根這是定義沒有任何例外。第二個(gè)觀察得到根結(jié)點(diǎn)之后去中序序列里找到這個(gè)根根左邊的所有結(jié)點(diǎn)一定屬于左子樹根右邊的所有結(jié)點(diǎn)一定屬于右子樹。中序遍歷的順序是“左、根、右”所以根天然地把結(jié)點(diǎn)分成左右兩個(gè)部分。第三個(gè)觀察也是最重要的左子樹和右子樹的結(jié)點(diǎn)在先序序列中也必須是連續(xù)的兩段。先序遍歷的順序是“根、左、右”根訪問完之后緊接著訪問整棵左子樹左子樹訪問完才訪問右子樹。因此如果中序序列告訴我們左子樹有 L 個(gè)結(jié)點(diǎn)那么先序序列中緊隨根之后的 L 個(gè)結(jié)點(diǎn)必須全部屬于左子樹集合再往后的結(jié)點(diǎn)必須全部屬于右子樹集合。這三個(gè)觀察合在一起就構(gòu)成了“先序中序唯一確定二叉樹”的證明過程同時(shí)也是判斷“序列是否合法”的判定規(guī)則。用一個(gè)小例子演示這個(gè)過程。假設(shè)先序序列是 ABDCE中序序列是 DBAEC。先取先序第一個(gè)元素 A 作為根在中序 DBAEC 中找到 A位置在中間偏右。A 左邊是 DB說明左子樹集合是 {D, B}A 右邊是 EC說明右子樹集合是 {E, C}。再看先序序列 ABDCE。根 A 之后是 B、D、C、E 這 4 個(gè)結(jié)點(diǎn)。左子樹有 2 個(gè)結(jié)點(diǎn)所以先序中 A 之后的 2 個(gè)結(jié)點(diǎn) B、D 必須屬于左子樹集合確實(shí) {B, D} {D, B}。剩下 C、E 屬于右子樹集合確實(shí) {C, E} {E, C}。第一層驗(yàn)證通過。接下來遞歸驗(yàn)證左子樹。左子樹的先序片段是 BD中序片段是 DB。根是 B中序中 B 的左邊是 D說明左子樹的左子樹是 {D}右子樹為空。再看左子樹先序 BD根 B 之后是 D正好屬于左子樹集合。驗(yàn)證通過。右子樹同理先序 CE中序 EC根 C左子樹 E驗(yàn)證通過。因此這兩個(gè)序列確實(shí)來自同一棵樹。這里的關(guān)鍵在于每一次分割后都要用“左子樹結(jié)點(diǎn)數(shù)”去切割先序序列。左子樹有多少個(gè)結(jié)點(diǎn)根后面的前多少個(gè)位置就必須是左子樹的先序片段。這就是“約束”二字的真正含義。如果某個(gè)中序序列給出的左子樹集合和先序序列中緊隨根后的結(jié)點(diǎn)集合對(duì)不上那就說明這個(gè)中序序列不可能是該先序序列對(duì)應(yīng)的任何一棵二叉樹的中序序列。這就是 2011 年第 5 題所有“不可能”選項(xiàng)的根源。3. 手算解法30秒排除不可能的“三步法”選擇題不需要真的把整棵樹完整還原。絕大多數(shù)選項(xiàng)在第一層驗(yàn)證時(shí)就能排除。這里給出一個(gè)適合考場(chǎng)上使用的手算三步法。3.1 三步法總覽第一步確定根。先序序列的第一個(gè)元素就是當(dāng)前子樹的根。第二步在中序序列中找到根的位置。根左邊有多少個(gè)結(jié)點(diǎn)就說明左子樹有多少個(gè)結(jié)點(diǎn)根右邊有多少個(gè)結(jié)點(diǎn)就說明右子樹有多少個(gè)結(jié)點(diǎn)。第三步用左子樹結(jié)點(diǎn)數(shù)去切割先序序列。先序序列中根后面的前 L 個(gè)結(jié)點(diǎn)必須全部來自中序中根左邊的集合后 n-L-1 個(gè)結(jié)點(diǎn)必須全部來自中序中根右邊的集合。如果匹配對(duì)左子樹和右子樹繼續(xù)遞歸驗(yàn)證如果不匹配直接判定不可能。這個(gè)方法的本質(zhì)就是把“先序中序唯一確定二叉樹”的證明過程反著用。每一層只需要做一件事檢查“先序中緊跟根的那一段”和“中序中根左右兩段”是否集合一致。3.2 手算實(shí)例先序 ABCDEF中序 CABDEF用先序 ABCDEF 和中序 CABDEF 走一遍完整流程。先序第一個(gè)元素是 AA 就是整棵樹的根。在中序 CABDEF 中找到 A位置在第 2 個(gè)下標(biāo)從 1 開始。A 的左邊只有一個(gè)結(jié)點(diǎn) C說明左子樹集合是 {C}左子樹大小為 1。A 的右邊是 B、D、E、F說明右子樹集合是 {B, D, E, F}?，F(xiàn)在用左子樹大小 1 去切割先序。先序是 A、B、C、D、E、F根 A 之后應(yīng)該是 1 個(gè)左子樹結(jié)點(diǎn)也就是 B?？墒?B 并不在左子樹集合 {C} 中而是屬于右子樹集合。這就矛盾了如果 B 是 A 的左孩子它應(yīng)該出現(xiàn)在中序 A 的左邊但中序 A 的左邊只有 C如果 B 不是左孩子那左子樹大小就不是 1而先序中 A 后緊接著就是 B這與“先序先遍歷左子樹”矛盾。所以 CABDEF 不可能成為先序 ABCDEF 對(duì)應(yīng)二叉樹的中序序列。整個(gè)過程只需要十幾秒不需要畫樹。3.3 容易忽略的遞歸驗(yàn)證三步法中第三步看起來只是集合判斷但要注意集合判斷只是必要條件不是充分條件。第一層通過后左右子樹內(nèi)部仍然可能存在矛盾。舉例來說先序 ABCDEF中序 CBADEF。第一層檢查根 A中序中 A 左邊是 CB左子樹集合 {C, B}左子樹大小 2先序 A 后是 B、C恰好都屬于左子樹集合右邊 D、E、F 都屬于右子樹集合。第一層通過。但如果就此判定合法是不夠嚴(yán)謹(jǐn)?shù)摹＿€要繼續(xù)看左子樹左子樹先序片段是 BC中序片段是 CB。根 B中序中 B 的左邊是 C左子樹集合 {C}左子樹大小 1再看先序 BC根 B 后是 CC 確實(shí)在左子樹集合中驗(yàn)證通過。右子樹先序 DEF中序 DEF根 D右子樹 EF同樣通過。因此 CBADEF 確實(shí)合法。在選擇題里出題人經(jīng)常會(huì)把干擾項(xiàng)設(shè)計(jì)成“第一層看起來沒問題但子樹內(nèi)部有問題”的形式。所以手算時(shí)至少要做到第二層、第三層的遞歸驗(yàn)證不能只驗(yàn)證根這一層就下結(jié)論。4. 完整示例先序 ABCDEF 的四種中序誰不可能下面用一組典型的選項(xiàng)設(shè)計(jì)來演示完整判斷過程。給定先序序列 ABCDEF有四個(gè)中序序列候選A. A B C D E FB. B A C D E FC. C B A D E FD. C A B D E F用三步法逐個(gè)驗(yàn)證。先看選項(xiàng) A中序 ABCDEF。根是 A中序中 A 在最左邊說明左子樹為空右子樹結(jié)點(diǎn)集合是 {B, C, D, E, F}。先序中 A 后面的 B C D E F 全部屬于右子樹集合長(zhǎng)度也正確。進(jìn)一步檢查右子樹先序 BCDEF中序 BCDEF根 B同樣結(jié)構(gòu)。這說明整棵樹是一條只向右延伸的鏈A 的右孩子是 BB 的右孩子是 C以此類推。選項(xiàng) A 合法。再看選項(xiàng) B中序 BACDEF。根 A 在中序中位于第 2 位左邊只有 B左子樹集合 {B}右子樹集合 {C, D, E, F}。先序中 A 后第一個(gè)是 B確實(shí)屬于左子樹集合且左子樹大小為 1剩下的 C D E F 屬于右子樹集合。驗(yàn)證通過。對(duì)應(yīng)樹的結(jié)構(gòu)是A 的左孩子是 BA 的右子樹是 C-D-E-F 這條右鏈。選項(xiàng) B 合法。接著看選項(xiàng) C中序 CBADEF。根 A 左邊是 CB左子樹集合 {C, B}大小為 2右邊是 DEF右子樹集合 {D, E, F}。先序中 A 后是 B、C這兩個(gè)正好屬于左子樹集合長(zhǎng)度 2后面的 D、E、F 屬于右子樹集合。第一層通過。再看左子樹先序 BC中序 CB根 B左子樹為 C可以匹配。選項(xiàng) C 合法。最后看選項(xiàng) D中序 CABDEF。根 A 左邊只有一個(gè) C左子樹集合是 {C}左子樹大小為 1右邊是 B、D、E、F。先序中 A 后第一個(gè)結(jié)點(diǎn)是 B但 B 并不在左子樹集合 {C} 中而是屬于右子樹集合。和 3.2 節(jié)的分析一樣B 的位置無法安放。因此選項(xiàng) D 是中序序列不可能出現(xiàn)的情況。這道題選 D。選項(xiàng) D 是很好的干擾項(xiàng)因?yàn)樗雌饋怼昂苡兄行虻母杏X”A 在中間左右各有一堆結(jié)點(diǎn)。但正是這種表面上的“合理”讓人忽略了先序和中序之間的連續(xù)段約束。再換一個(gè)角度理解如果把先序序列看成入棧順序把中序序列看成出棧順序那么 CABDEF 這個(gè)出棧順序在棧模擬中會(huì)在第二個(gè)位置卡住。A 入棧后B 入棧此時(shí) B 壓在 A 上面如果第一個(gè)出棧的是 C那么必須先把 A、B 都?jí)哼M(jìn)去C 出棧后棧頂是 B但中序第二個(gè)元素是 A而 A 被 B 壓住無法立即出棧。矛盾由此產(chǎn)生。這個(gè)棧的視角非常重要后面寫代碼時(shí)最簡(jiǎn)潔的合法性判斷就是基于這個(gè)思路實(shí)現(xiàn)的。5. 代碼實(shí)現(xiàn)用棧模擬判斷中序序列是否合法選擇題用手算三步法已經(jīng)足夠。但如果想徹底檢驗(yàn)自己的理解或者為復(fù)試機(jī)試做準(zhǔn)備就應(yīng)該把判斷邏輯寫成代碼。5.1 算法思路先序是入棧序中序是出棧序非遞歸中序遍歷二叉樹時(shí)會(huì)用到棧。中序遍歷的訪問順序正好對(duì)應(yīng)著一種“按先序入棧、按中序出?！钡哪M過程先序序列決定結(jié)點(diǎn)什么時(shí)候入棧中序序列決定結(jié)點(diǎn)什么時(shí)候出棧。算法過程如下維護(hù)一個(gè)棧初始為空。用指針 i 指向先序序列表示下一個(gè)待入棧的結(jié)點(diǎn)。從左到右掃描中序序列的每個(gè)字符 c當(dāng)棧為空或者棧頂元素不等于 c 時(shí)不斷從先序序列中取元素入棧直到棧頂元素等于 c或者先序序列已經(jīng)全部入棧。如果先序序列已經(jīng)用盡棧頂仍然不等于 c說明這個(gè)中序序列不可能出現(xiàn)返回 false。如果棧頂?shù)扔?c彈出棧頂繼續(xù)處理中序下一個(gè)字符。如果中序序列掃描完說明所有字符都正確匹配返回 true。每個(gè)字符最多入棧一次、出棧一次所以時(shí)間復(fù)雜度是 O(n)其中 n 是序列長(zhǎng)度。5.2 C 語言完整實(shí)現(xiàn)#include stdio.h #include string.h #include stdbool.h #define MAXN 100 // 判斷中序序列 in 是否可能是先序序列 pre 對(duì)應(yīng)二叉樹的中序遍歷 bool isValidInorder(const char *pre, const char *in, int n) { char stack[MAXN]; int top -1; int i 0; // pre 序列的指針 for (int j 0; j n; j) { // ?？栈驐ｍ敳坏扔诋?dāng)前中序字符時(shí)繼續(xù)入棧 while (top -1 || stack[top] ! in[j]) { if (i n) { return false; // 先序元素全部入棧仍無法匹配 } stack[top] pre[i]; } // 匹配成功出棧 top--; } return true; } int main() { char pre[MAXN], in[MAXN]; printf(請(qǐng)輸入先序遍歷序列: ); scanf(%s, pre); printf(請(qǐng)輸入中序遍歷序列: ); scanf(%s, in); int n strlen(pre); if (strlen(in) ! n) { printf(兩個(gè)序列長(zhǎng)度不一致輸入錯(cuò)誤\n); return 0; } if (isValidInorder(pre, in, n)) { printf(該中序序列合法對(duì)應(yīng)二叉樹存在\n); } else { printf(該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生\n); } return 0; }核心邏輯集中在isValidInorder中。stack[top] pre[i]這一步把先序序列中的元素依次壓棧直到棧頂能匹配當(dāng)前要處理的中序字符。如果先序序列已經(jīng)全部壓入棧中還沒有匹配成功說明棧里剩余元素的順序和中序序列沖突該中序序列不合法。編譯和運(yùn)行命令如下gcc btree_inorder_check.c -o btree_inorder_check ./btree_inorder_check輸入一組合法序列例如先序 ABCDEF、中序 CBADEF程序輸出請(qǐng)輸入先序遍歷序列: ABCDEF 請(qǐng)輸入中序遍歷序列: CBADEF 該中序序列合法對(duì)應(yīng)二叉樹存在輸入一組非法序列例如先序 ABCDEF、中序 CABDEF程序輸出請(qǐng)輸入先序遍歷序列: ABCDEF 請(qǐng)輸入中序遍歷序列: CABDEF 該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生5.3 Python 精簡(jiǎn)版如果平時(shí)用 Python 刷題可以用下面這個(gè)更精簡(jiǎn)的版本def is_valid_inorder(pre: str, in_order: str) - bool: stack [] i 0 for ch in in_order: while not stack or stack[-1] ! ch: if i len(pre): return False stack.append(pre[i]) i 1 stack.pop() return True if __name__ __main__: pre input(請(qǐng)輸入先序遍歷序列: ).strip() in_order input(請(qǐng)輸入中序遍歷序列: ).strip() if len(pre) ! len(in_order): print(兩個(gè)序列長(zhǎng)度不一致) elif is_valid_inorder(pre, in_order): print(該中序序列合法對(duì)應(yīng)二叉樹存在) else: print(該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生)Python 版本的邏輯和 C 版本完全一致。這里要注意一個(gè)容易出錯(cuò)的點(diǎn)while not stack or stack[-1] ! ch這個(gè)條件中必須先判斷棧是否為空再判斷棧頂順序不能寫反否則空棧訪問stack[-1]會(huì)報(bào) IndexError。機(jī)試時(shí)這個(gè)棧模擬函數(shù)可以作為判斷“遍歷序列是否配對(duì)”的通用工具也可以進(jìn)一步用于重建二叉樹。6. 進(jìn)階合法時(shí)重建二叉樹并驗(yàn)證后序判斷合法性只是第一步。408 的大題和復(fù)試機(jī)試?yán)锝?jīng)常要求“給定先序和中序重建二叉樹并輸出后序”。這個(gè)需求可以在合法性的基礎(chǔ)上直接擴(kuò)展。6.1 遞歸重建的核心邏輯構(gòu)建過程和前面手算三步法一模一樣先序片段的第一個(gè)元素是根。在中序片段中找到根的位置 pos。中序片段中pos 左邊是左子樹中序pos 右邊是右子樹中序。左子樹結(jié)點(diǎn)數(shù) leftLen pos - inL用它把先序片段切成三部分根、左子樹先序、右子樹先序。遞歸構(gòu)建左右子樹。邊界條件很簡(jiǎn)單當(dāng)先序片段的左邊界大于等于右邊界時(shí)說明沒有結(jié)點(diǎn)返回 NULL。6.2 C 語言重建并輸出后序完整代碼#include stdio.h #include stdlib.h #include string.h #include stdbool.h #define MAXN 100 typedef struct TreeNode { char val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 判斷中序序列是否可能 bool isValidInorder(const char *pre, const char *in, int n) { char stack[MAXN]; int top -1; int i 0; for (int j 0; j n; j) { while (top -1 || stack[top] ! in[j]) { if (i n) return false; stack[top] pre[i]; } top--; } return true; } // 根據(jù)先序和中序重建二叉樹 TreeNode *buildTree(const char *pre, int preL, int preR, const char *in, int inL, int inR) { if (preL preR) { return NULL; } TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-val pre[preL]; // 在中序片段中查找根的位置 int pos inL; while (pos inR in[pos] ! pre[preL]) { pos; } int leftLen pos - inL; // 左子樹結(jié)點(diǎn)數(shù) // 左子樹先序 [preL1, preL1leftLen)中序 [inL, pos) node-left buildTree(pre, preL 1, preL 1 leftLen, in, inL, pos); // 右子樹先序 [preL1leftLen, preR)中序 [pos1, inR) node-right buildTree(pre, preL 1 leftLen, preR, in, pos 1, inR); return node; } void postorder(TreeNode *root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%c, root-val); } int main() { char pre[MAXN], in[MAXN]; printf(請(qǐng)輸入先序遍歷序列: ); scanf(%s, pre); printf(請(qǐng)輸入中序遍歷序列: ); scanf(%s, in); int n strlen(pre); if (strlen(in) ! n) { printf(兩個(gè)序列長(zhǎng)度不一致輸入錯(cuò)誤\n); return 0; } if (!isValidInorder(pre, in, n)) { printf(該中序序列不可能由該先序序列對(duì)應(yīng)的二叉樹產(chǎn)生\n); } else { printf(該中序序列合法\n); TreeNode *root buildTree(pre, 0, n, in, 0, n); printf(重建成功后序遍歷序列為: ); postorder(root); printf(\n); } return 0; }這段代碼把“判斷”和“重建”放在了一起。運(yùn)行示例請(qǐng)輸入先序遍歷序列: ABCDEF 請(qǐng)輸入中序遍歷序列: CBADEF 該中序序列合法 重建成功后序遍歷序列為: CBFEDA可以用前面的手算過程驗(yàn)證這個(gè)后序結(jié)果。先序 ABCDEF、中序 CBADEF 對(duì)應(yīng)這棵樹A 是根。左子樹先序 BC中序 CB根 B左孩子 C。右子樹先序 DEF中序 DEF根 D右孩子 EE 的右孩子 F。后序遍歷順序是“左、右、根”C左子樹最左葉子、B左子樹根、F右子樹最右葉子、E、D、A也就是 CBFEDA。和程序輸出一致。如果 n 很大遞歸中用循環(huán)找根的位置是 O(n) 的整體會(huì)退化到 O(n^2)。面試或機(jī)試中更穩(wěn)妥的做法是先用哈希表記錄中序序列中每個(gè)字符的下標(biāo)把查找根的位置優(yōu)化到 O(1)。哈希優(yōu)化版本需要注意一個(gè)前提二叉樹中所有結(jié)點(diǎn)值互不相同。如果存在重復(fù)值哈希表會(huì)丟失信息這也是 408 題目默認(rèn)的前提條件。7. 常見錯(cuò)誤與排查思路代碼和手算都容易踩坑。下面把出現(xiàn)頻率較高的幾個(gè)問題整理出來。問題現(xiàn)象可能原因排查方式解決方案手算認(rèn)為合法程序判斷非法兩個(gè)序列的參數(shù)順序傳反或輸入時(shí)有空格打印 pre 和 in確認(rèn)誰是誰統(tǒng)一按“先序在前、中序在后”調(diào)用元素集合相同但長(zhǎng)度一致仍判斷非法序列中存在重復(fù)字符逐字符檢查重復(fù)值會(huì)導(dǎo)致棧模擬歧義408 默認(rèn)結(jié)點(diǎn)值互異如果確實(shí)重復(fù)需要帶編號(hào)處理遞歸重建時(shí)棧溢出二叉樹退化成一條鏈遞歸深度等于結(jié)點(diǎn)數(shù)輸出樹高或檢查輸入序列是否來自極端樹形機(jī)試可改用迭代棧模擬筆試直接說明遞歸思路只驗(yàn)證根一層就下結(jié)論左子樹或右子樹內(nèi)部仍然存在矛盾對(duì)左右子樹遞歸執(zhí)行三步法至少遞歸到第二層必要時(shí)畫樹驗(yàn)證哈希優(yōu)化后結(jié)果錯(cuò)誤中序存在重復(fù)字符哈希表覆蓋了位置信息打印哈希表內(nèi)容檢查有重復(fù)值時(shí)不能直接用普通哈希表其中最常見的問題是把“集合相等”當(dāng)作“序列合法”。集合相等只是必要條件遞歸結(jié)構(gòu)也必須一致。比如先序 ABC、中序 CAB根 A 左邊是 C右邊是 B左子樹集合 {C}但先序中 A 后第一個(gè)是 BB 不在左子樹集合中所以非法。這里的矛盾發(fā)生在第一層很容易看出來。但有些題目會(huì)把矛盾藏在子樹內(nèi)部第一層集合完全匹配到第二層才暴露。做題時(shí)如果遇到兩個(gè)選項(xiàng)第一層都通過必須繼續(xù)往下驗(yàn)證子樹這就是遞歸思想的實(shí)際應(yīng)用。另一個(gè)高發(fā)問題是遞歸重建時(shí)邊界寫錯(cuò)。buildTree函數(shù)里左子樹的先序范圍是[preL1, preL1leftLen)右子樹的范圍是[preL1leftLen, preR)。很多同學(xué)會(huì)把右子樹的起點(diǎn)寫成preLleftLen少加一個(gè) 1導(dǎo)致跳過根結(jié)點(diǎn)。判斷邊界時(shí)可以打印每次遞歸的參數(shù)來核對(duì)。這個(gè)錯(cuò)誤在代碼中很難一眼發(fā)現(xiàn)但一旦輸出后序結(jié)果完全錯(cuò)亂基本就是邊界問題。8. 408復(fù)習(xí)建議與擴(kuò)展考點(diǎn)2011 年第 5 題屬于“遍歷序列恢復(fù)二叉樹”這一大考點(diǎn)。這類題目在 408 中反復(fù)出現(xiàn)而且換湯不換藥。下面把這些考點(diǎn)串起來復(fù)習(xí)效率會(huì)高很多。8.1 不同序列組合能否唯一確定二叉樹給定序列能否唯一確定二叉樹說明先序 中序能先序定根中序分左右后序 中序能后序定根中序分左右層次 中序能層次序定根順序中序分左右先序 后序不能單孩子結(jié)點(diǎn)的左右方向無法區(qū)分先序 空指針標(biāo)記能空指針標(biāo)記補(bǔ)全了左右子樹信息“先序 后序不能唯一確定”這個(gè)結(jié)論可以用最簡(jiǎn)反例說明兩個(gè)結(jié)點(diǎn)的樹根 A 的左孩子是 B和根 A 的右孩子是 B這兩種樹的先序序列都是 AB后序序列都是 BA但中序一個(gè)是 BA一個(gè)是 AB是兩棵不同的二叉樹。所以考試中只要出現(xiàn)“先序 后序還原二叉樹”的說法可以直接判斷為錯(cuò)誤或需要額外條件。8.2 與本題相似的考法第一類給后序 中序求先序。做法和先序 中序完全對(duì)稱只是要把“先序第一個(gè)元素是根”換成“后序最后一個(gè)元素是根”然后同樣用中序切割左右子樹。第二類給先序 后序問中序有多少種可能。這種題考查的是對(duì)“單孩子結(jié)點(diǎn)”的理解。每當(dāng)一個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)這個(gè)孩子在先序和后序中的相對(duì)位置體現(xiàn)不出左右對(duì)應(yīng)中序就多一種可能。第三類在二叉排序樹背景下考查遍歷。二叉排序樹的中序遍歷一定是遞增序列所以“二叉排序樹先序 中序”的組合里中序其實(shí)已經(jīng)隱含了結(jié)點(diǎn)之間的順序關(guān)系這類題通常和查找、插入結(jié)合。第四類把遍歷和棧結(jié)合。中序遍歷的非遞歸實(shí)現(xiàn)依賴棧所以“先序?yàn)槿霔ｍ樞?、中序?yàn)槌鰲ｍ樞颉边@個(gè)模型本身就是考點(diǎn)。掌握了棧模擬判斷法這類題基本是送分題。8.3 復(fù)習(xí)建議給四個(gè)可落地的建議第一先把三種遍歷的手算過關(guān)包括遞歸版本和非遞歸版本。不要只背代碼要能在紙上快速寫出任意一棵樹的先序、中序、后序。第二做“遍歷序列恢復(fù)二叉樹”的專項(xiàng)練習(xí)每天手算三題。題目不用很難重點(diǎn)是訓(xùn)練“先序定根、中序分割、左子樹長(zhǎng)度切先序”這三個(gè)動(dòng)作直到形成條件反射。第三機(jī)試必練三件事棧模擬判斷合法性、遞歸重建二叉樹、輸出另一種遍歷驗(yàn)證結(jié)果。這三個(gè)能力可以互相驗(yàn)證也是復(fù)試機(jī)試的高頻考點(diǎn)。第四錯(cuò)題本里不要只抄原題答案。把“通用解法”寫下來比如 2011 年第 5 題的通用解法就是“三步法 遞歸驗(yàn)證”下次遇到同類題直接調(diào)用這套思路而不是回憶上次選的是 A 還是 D。9. 總結(jié)與動(dòng)手練習(xí)這篇文章把 2011 年第 5 題背后的邏輯拆成了三層原理層理解先序 中序?yàn)槭裁茨芪ㄒ淮_定一棵二叉樹手算層用“三步法”快速判斷中序序列是否合法代碼層用棧模擬判斷合法性用遞歸重建二叉樹并輸出后序。其中最關(guān)鍵的一個(gè)認(rèn)知是兩個(gè)序列來自同一棵樹時(shí)先序序列中緊隨根之后的左子樹結(jié)點(diǎn)段長(zhǎng)度必須等于中序序列中根左邊結(jié)點(diǎn)的數(shù)量且這兩個(gè)集合必須一致。這個(gè)約束條件既是證明“唯一確定”的依據(jù)也是判斷“不可能”的武器。下面留三道練習(xí)題建議先手算再用代碼驗(yàn)證最后在評(píng)論區(qū)交流答案。已知先序序列為 ABCDEF中序序列為 CDBAEF這個(gè)中序序列是否合法如果合法后序序列是什么已知后序序列為 DEBFCA中序序列為 DBEAFC求先序序列。為什么“先序 后序”不能唯一確定一棵二叉樹請(qǐng)畫出一個(gè)具體反例。把 2011 年第 5 題吃透之后你會(huì)明顯感覺到408 數(shù)據(jù)結(jié)構(gòu)中對(duì)二叉樹遍歷的考查表面上是選擇題本質(zhì)上是讓你在腦子里維護(hù)一棵樹。當(dāng)你面對(duì)任意一組先序和中序序列能在幾十秒內(nèi)判斷出“這棵樹到底存不存在”時(shí)這一類題就已經(jīng)真正通了。