上個(gè)月幫一個(gè)準(zhǔn)備考研的朋友做數(shù)據(jù)結(jié)構(gòu)串講聊到二叉樹那一章他跟我說“前面的鏈表還能畫圖硬推到了樹這里遞歸一上代碼就徹底看不懂了。”這句話我太熟了。幾乎每個(gè)剛開始碰數(shù)據(jù)結(jié)構(gòu)的人都會卡在同一個(gè)位置上不是不知道“先序、中序、后序”這三個(gè)口訣而是不知道遞歸在底層到底怎么跑更不知道這些遍歷序列組合起來還能還原出一整棵樹。今天這篇就專門把二叉樹這塊掰開揉碎講一遍從結(jié)點(diǎn)定義、四種遍歷、深度計(jì)算到根據(jù)先序中序還原二叉樹再到搜索二叉樹、AVL樹、線索二叉樹這些高頻考點(diǎn)一次串個(gè)完整。無論你是考研、期末突擊、軟考還是面試前臨時(shí)抱佛腳刷數(shù)據(jù)結(jié)構(gòu)拿這篇文章當(dāng)索引照著過會比翻教材來得更快。1. 二叉樹在數(shù)據(jù)結(jié)構(gòu)里的位置1.1 為什么只分“左”和“右”鏈表、棧、隊(duì)列這類線性結(jié)構(gòu)處理的是“一對一”的關(guān)系每個(gè)結(jié)點(diǎn)最多只有一個(gè)直接后繼。但現(xiàn)實(shí)里的數(shù)據(jù)關(guān)系遠(yuǎn)不止“一排排站著”文件目錄套子目錄、公司組織架構(gòu)、編譯器的語法分析樹全是“一對多”的層級關(guān)系。要表達(dá)這種關(guān)系就需要非線性結(jié)構(gòu)而樹是最自然的模型。那為什么偏偏是“二叉樹”而不是三叉樹、四叉樹兩個(gè)原因。第一兩個(gè)分支足夠表達(dá)任意多叉結(jié)構(gòu)。把多叉樹轉(zhuǎn)成二叉樹有一個(gè)很經(jīng)典的方法叫“左孩子右兄弟”也就是說任意一棵樹都能用“左指針指向第一個(gè)孩子右指針指向下一個(gè)兄弟”的方式轉(zhuǎn)成二叉樹信息量一點(diǎn)不丟。第二兩個(gè)分支讓代碼結(jié)構(gòu)異常簡潔。你寫遞歸的時(shí)候就知道了左子樹右子樹各處理一次邏輯是天然的二分。二叉樹還有一個(gè)特殊品類叫“完全二叉樹”它每一層都從左往右鋪滿只有最后一層允許缺右側(cè)結(jié)點(diǎn)。完全二叉樹因?yàn)樾蛱栠B續(xù)可以直接用數(shù)組存父節(jié)點(diǎn)下標(biāo)和子節(jié)點(diǎn)下標(biāo)之間有著漂亮的數(shù)學(xué)關(guān)系堆排序、優(yōu)先隊(duì)列全建立在這個(gè)關(guān)系上面?？梢哉f二叉樹是“既能理解樹結(jié)構(gòu)又能適配計(jì)算機(jī)存儲”的最佳折中。1.2 這幾個(gè)基礎(chǔ)概念建議刻進(jìn)腦子里有些概念到面試前還在混淆我直接列一個(gè)最小清單結(jié)點(diǎn)的度結(jié)點(diǎn)擁有的子樹個(gè)數(shù)二叉樹里度只能是0、1、2。葉子結(jié)點(diǎn)度為0的結(jié)點(diǎn)也叫終端結(jié)點(diǎn)。樹的深度高度根結(jié)點(diǎn)到最遠(yuǎn)葉子結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)層數(shù)。按“根在第1層”算只有一個(gè)根的樹深度是1空樹深度是0。滿二叉樹每一層都滿第k層有2^(k-1)個(gè)結(jié)點(diǎn)。完全二叉樹除了最后一層上面都是滿的最后一層結(jié)點(diǎn)從左往右連續(xù)排列中間不能有空檔。還有一個(gè)經(jīng)常出現(xiàn)在選擇題里的結(jié)論對于任何一棵非空二叉樹葉子結(jié)點(diǎn)數(shù) n0 等于度為2的結(jié)點(diǎn)數(shù) n2 加1也就是 n0 n2 1。這個(gè)結(jié)論可以快速證明設(shè)總結(jié)點(diǎn)數(shù) n n0 n1 n2邊的數(shù)量 m n - 1每個(gè)結(jié)點(diǎn)除了根都有一條邊指向它同時(shí) m 0n0 1n1 2*n2 n1 2n2。聯(lián)立可得 n0 n2 1。這個(gè)推導(dǎo)幾乎每年考研選擇題都有別死記自己推一遍就忘不了。1.3 二叉樹在真實(shí)系統(tǒng)里解決什么問題很多人學(xué)二叉樹覺得“這東西只活在考試?yán)铩逼鋵?shí)二叉樹的應(yīng)用比想象中密集。最典型的是表達(dá)式求值一個(gè)四則運(yùn)算表達(dá)式可以解析成表達(dá)式樹葉子是操作數(shù)內(nèi)部結(jié)點(diǎn)是運(yùn)算符后序遍歷這棵樹就能得到后綴表達(dá)式計(jì)算機(jī)拿后綴表達(dá)式做棧運(yùn)算非常順。再比如哈夫曼樹根據(jù)字符頻率構(gòu)建帶權(quán)路徑最短的二叉樹壓縮算法里常見的哈夫曼編碼就是靠它生成的。數(shù)據(jù)庫里的B樹索引雖然不嚴(yán)格是二叉樹但從二叉搜索樹一路平衡化、多路化的演化路徑本質(zhì)上就是二叉樹思維的延伸。堆是一種用完全二叉樹實(shí)現(xiàn)的結(jié)構(gòu)操作系統(tǒng)調(diào)度、TopK問題都在用。理解了二叉樹再看這些工程結(jié)構(gòu)會輕松很多。2. 先動(dòng)手把一棵樹存起來2.1 三種存儲方式考試和工程各用哪個(gè)二叉樹的存儲方式主要有兩種思路一種是順序存儲用數(shù)組另一種是鏈?zhǔn)酱鎯τ弥羔?。順序存儲的核心是給結(jié)點(diǎn)編號根結(jié)點(diǎn)存下標(biāo)0那么對于下標(biāo)為 i 的結(jié)點(diǎn)左孩子下標(biāo)是 2i 1右孩子是 2i 2父節(jié)點(diǎn)是 (i-1)/2。這種存儲對完全二叉樹極其友好幾乎不浪費(fèi)空間而且父找子、子找父都只要一個(gè)公式。但普通二叉樹如果用數(shù)組存中間會有大量空位極端情況下一個(gè)只有右鏈的“斜樹”數(shù)組長度要求是2的k次方級別空間浪費(fèi)嚴(yán)重。鏈?zhǔn)酱鎯t長得很像語言里的結(jié)構(gòu)體每個(gè)結(jié)點(diǎn)自帶兩個(gè)指針?？荚嚭兔嬖?yán)锝^大多數(shù)題目都是基于鏈?zhǔn)蕉鏄涞囊驗(yàn)檫f歸操作左子樹右子樹太自然了。三叉鏈表是二叉鏈表的增強(qiáng)版多了一個(gè)指向父節(jié)點(diǎn)的指針某些題目要求找父節(jié)點(diǎn)或者回溯時(shí)會用到但日常做題碰得少。對比下來順序存儲適合“空間緊湊的完全二叉樹”鏈?zhǔn)酱鎯m合“任意形態(tài)的二叉樹以及需要頻繁增刪改的場景”。選擇題喜歡問這個(gè)記住一個(gè)關(guān)鍵印象詞完全二叉樹用順序普通二叉樹用鏈?zhǔn)健?.2 二叉鏈表定義與“空指針域”的秘密C語言的二叉鏈表定義就是嚴(yán)蔚敏教材里那個(gè)經(jīng)典結(jié)構(gòu)typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;Python里對應(yīng)寫成類class TreeNode: def __init__(self, val): self.val val self.left None self.right None這里有一個(gè)特別愛考的小結(jié)論n個(gè)結(jié)點(diǎn)的二叉鏈表一共有 2n 個(gè)指針域其中真正指向孩子的指針數(shù)等于邊數(shù) n-1所以空指針域的數(shù)量是 2n - (n-1) n1。也就是說一棵有10個(gè)結(jié)點(diǎn)的二叉樹它的鏈?zhǔn)酱鎯镆欢ㄓ?1個(gè)空指針。這個(gè)數(shù)字看起來平平無奇但它就是后面線索二叉樹的地基——線索二叉樹就是把這些空指針“廢物利用”起來存前驅(qū)和后繼信息。2.3 用先序擴(kuò)展序列創(chuàng)建一棵二叉樹創(chuàng)建一個(gè)二叉樹最直觀的方式是“手動(dòng)new結(jié)點(diǎn)再連接”但在代碼題里更常見的是給出一個(gè)先序擴(kuò)展序列讓你遞歸建樹。所謂擴(kuò)展序列就是遇到空孩子的位置用一個(gè)特殊符號比如#占位。比如先序序列ABD##E##C##對應(yīng)一棵根為A、左孩子為B、右孩子為CB的左孩子為D、右孩子為E的樹。C語言實(shí)現(xiàn)長這樣void CreateBiTree(BiTree *T) { char ch; scanf( %c, ch); if (ch #) { *T NULL; } else { *T (BiTree)malloc(sizeof(BiTNode)); (*T)-data ch; CreateBiTree((*T)-lchild); CreateBiTree((*T)-rchild); } }注意幾個(gè)細(xì)節(jié)。第一scanf的格式串里那個(gè)空格很關(guān)鍵它能跳過前一次輸入殘留的換行符不然代碼會莫名其妙讀錯(cuò)字符。第二函數(shù)參數(shù)用的是二級指針 BiTree *T因?yàn)槲覀円诤瘮?shù)內(nèi)部修改指針本身的值讓它指向新分配的結(jié)點(diǎn)一級指針傳進(jìn)去只能修改指針指向的內(nèi)容改不了指針本身。這也是C語言里最常見的坑之一很多初學(xué)者就是在這里被繞暈。Python版本更簡單因?yàn)樗烊粋饕胐ef create_by_preorder(data): if not data: return None ch data.pop(0) if ch #: return None root TreeNode(ch) root.left create_by_preorder(data) root.right create_by_preorder(data) return root這個(gè)遞歸過程本身也透露了遍歷的順序先建根再建左子樹再建右子樹。把這行邏輯記住后面理解先序遍歷就順了。3. 遍歷先序、中序、后序、層序3.1 “序”的本質(zhì)是根的位置四種遍歷里先序、中序、后序都是深度優(yōu)先層序則是廣度優(yōu)先。很多人背口訣“根左右、左根右、左右根”背得很熟但一到具體題目就分不清。其實(shí)核心就一句話按“根被訪問的時(shí)機(jī)”命名。先序遍歷根最先被訪問然后訪問左子樹再訪問右子樹即根左右。中序遍歷先去左子樹逛一圈再訪問根最后去右子樹即左根右。后序遍歷先左、再右、最后才輪到根即左右根。舉一棵具體的樹A / \ B C / \ \ D E F先序遍歷結(jié)果A B D E C F 中序遍歷結(jié)果D B E A C F 后序遍歷結(jié)果D E B F C A 層序遍歷結(jié)果A B C D E F你看中序遍歷結(jié)果里A把序列分成左右兩半左邊D B E全是左子樹的結(jié)點(diǎn)右邊C F全是右子樹的結(jié)點(diǎn)。這個(gè)“中序序列天然能分離左右子樹”的性質(zhì)后面還原二叉樹時(shí)會用到極致。3.2 遞歸遍歷三行代碼換個(gè)位置就是另一種遍歷遞歸遍歷的代碼量少得驚人。以Python為例def preorder(root): if root is None: return print(root.val, end ) preorder(root.left) preorder(root.right) def inorder(root): if root is None: return inorder(root.left) print(root.val, end ) inorder(root.right) def postorder(root): if root is None: return postorder(root.left) postorder(root.right) print(root.val, end )三個(gè)函數(shù)結(jié)構(gòu)完全一樣只是 print 的位置不同。print 在最前就是先序在中間就是中序在最后就是后序。這個(gè)“三行代碼搞定三種遍歷”的版本一定要自己手敲幾遍敲多了你會有一種肌肉記憶。遞歸遍歷的核心是“信任遞歸”調(diào)用 preorder(root.left) 時(shí)你不需要在腦子里把整棵左子樹全部展開只需要相信這個(gè)調(diào)用能按先序把左子樹全部訪問完。很多初學(xué)者看遞歸喜歡一層一層往深處鉆鉆到第5層就亂了。正確姿勢是想清楚“當(dāng)前結(jié)點(diǎn)該做什么”和“子問題交給遞歸”然后設(shè)置好終止條件root is None時(shí)返回剩下的交給遞歸自己跑。3.3 非遞歸遍歷用棧把遞歸現(xiàn)場搬出來面試手撕題里非遞歸遍歷出現(xiàn)的概率高得離譜而且要求必須會用棧模擬。因?yàn)樵谧顗那闆r下二叉樹會退化成一條鏈遞歸深度等于結(jié)點(diǎn)數(shù)極易棧溢出所以生產(chǎn)環(huán)境里的樹操作常寫成非遞歸。先序非遞歸最簡單的寫法是“根入棧出棧訪問右孩子先入棧左孩子后入?！眃ef preorder_iter(root): if root is None: return stack [root] while stack: node stack.pop() print(node.val, end ) if node.right: stack.append(node.right) if node.left: stack.append(node.left)因?yàn)闂Ｊ呛筮M(jìn)先出入棧順序必須右先左后這樣彈出時(shí)才能保證左子樹先被訪問。這個(gè)反直覺的點(diǎn)特別容易寫反。中序非遞歸就更有意思了思路是“一路向左壓棧沒有左孩子就彈棧訪問然后轉(zhuǎn)向右子樹”def inorder_iter(root): stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() print(cur.val, end ) cur cur.right畫個(gè)圖就明白了先從根出發(fā)把根、根的左孩子、左孩子的左孩子……全部壓進(jìn)去直到最左下角。彈出一個(gè)結(jié)點(diǎn)并訪問這個(gè)結(jié)點(diǎn)沒有右孩子就繼續(xù)彈上一個(gè)有右孩子就移動(dòng)到右孩子再重復(fù)“一路向左”的過程。這個(gè)算法是筆試和面試的重災(zāi)區(qū)很多人死記代碼但下次還是忘建議找一棵具體的樹在紙上把棧的變化過程一步步寫出來寫一次就通了。后序非遞歸涉及“第二次經(jīng)過結(jié)點(diǎn)才能訪問”的問題需要加標(biāo)記或者用雙棧復(fù)雜度更高一點(diǎn)面試偶爾會考。我的建議是先把先序、中序理解透再碰后序不然很容易被繞暈。3.4 層序遍歷按層推進(jìn)的隊(duì)列思想層序遍歷的代碼沒有遞歸版本因?yàn)樗烊皇菑V度優(yōu)先廣度優(yōu)先的標(biāo)配結(jié)構(gòu)是隊(duì)列。from collections import deque def levelorder(root): if root is None: return q deque([root]) while q: node q.popleft() print(node.val, end ) if node.left: q.append(node.left) if node.right: q.append(node.right)流程很直白根先入隊(duì)出隊(duì)一個(gè)結(jié)點(diǎn)就訪問它同時(shí)把它的左右孩子接到隊(duì)尾。因?yàn)殛?duì)列是先進(jìn)先出所以上一層左邊結(jié)點(diǎn)的孩子會先于右邊結(jié)點(diǎn)的孩子被訪問這就實(shí)現(xiàn)了“按層從左往右掃”的效果。層序遍歷的變體很多比如求二叉樹的最大寬度、判斷是否是完全二叉樹都是在層序模板上改條件值得牢牢掌握。4. 二叉樹的深度遞歸和層序兩種解法4.1 深度、高度、層數(shù)教材差異別踩坑求深度這個(gè)事看起來簡單但每年都有不少人在概念上栽跟頭。深度和高度是兩個(gè)方向深度是從根往下數(shù)高度是從葉子往上數(shù)。對二叉樹整體來說根結(jié)點(diǎn)的深度等于樹的高度通常就是最大層數(shù)。但描述某個(gè)結(jié)點(diǎn)的時(shí)候這兩個(gè)值就不一樣了A結(jié)點(diǎn)的深度是它到根的距離高度是它到最遠(yuǎn)葉子的距離。還有些教材把根的深度規(guī)定為0而不是1這時(shí)候一棵6個(gè)結(jié)點(diǎn)的完全二叉樹深度就不是3而是2。不同教材、不同題庫的約定不一樣做題先看題目是否明確“根在第1層”。我一般建議默認(rèn)根在第1層遇到公式題再根據(jù)題目語境調(diào)整。4.2 遞歸求深度返回值是怎么一層層傳上去的求深度最常見的解法是遞歸代碼短到讓人懷疑int maxDepth(BiTree T) { if (T NULL) { return 0; } int leftDepth maxDepth(T-lchild); int rightDepth maxDepth(T-rchild); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }核心是一棵樹的深度 max(左子樹深度, 右子樹深度) 1。空樹深度是0作為遞歸出口。初學(xué)者最難理解的是返回值傳導(dǎo)?？辞懊婺强脴銩 / \ B C / \ \ D E FD、E、F都是葉子它們的左右孩子是NULL所以葉子結(jié)點(diǎn)的 leftDepth0、rightDepth0max取0再加1返回1表示葉子自身為1層。到B結(jié)點(diǎn)時(shí)左子樹D返回1右子樹E返回1B返回2。到C結(jié)點(diǎn)左孩子是NULL返回0右孩子F返回1C返回2。最后到A左子樹返回2右子樹返回2max取2再加1得到3。這就是整棵樹的深度。這個(gè)推導(dǎo)過程值得在紙上畫一遍它會把“遞歸返回值怎么一層層向上匯總”這件事徹底搞明白。4.3 層序求深度和完全二叉樹的深度公式遞歸求深度代碼簡單但在極端鏈?zhǔn)浇Y(jié)構(gòu)下遞歸深度太大可以用層序遍歷來求。思路是每次處理完一整層就深度加1def max_depth_level(root): if root is None: return 0 q deque([root]) depth 0 while q: size len(q) depth 1 for _ in range(size): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return depth每輪循環(huán)開始時(shí)隊(duì)列里的結(jié)點(diǎn)正好是同一層的全部結(jié)點(diǎn)用一次for循環(huán)把它們?nèi)繌棾鐾瑫r(shí)把下一層結(jié)點(diǎn)入隊(duì)循環(huán)結(jié)束后depth自然就加到了樹的層數(shù)。這個(gè)模板在求“最大寬度”時(shí)也能復(fù)用。完全二叉樹還有一種純數(shù)學(xué)求法結(jié)點(diǎn)數(shù)為 n 的完全二叉樹深度是 floor(log2 n) 1。比如6個(gè)結(jié)點(diǎn)的完全二叉樹log2(6)≈2.58取整是2加1等于3。這個(gè)公式在選擇題里能救命省去畫圖時(shí)間。5. 已知先序和中序還原整棵二叉樹5.1 為什么先序中序能唯一確定樹二叉樹的遍歷序列很像一副拼圖的碎片某些組合能完整復(fù)原某些組合不行。先序序列的第一個(gè)元素一定是根結(jié)點(diǎn)拿到根結(jié)點(diǎn)之后在中序序列里找到根的位置根左邊的元素全是左子樹的結(jié)點(diǎn)根右邊的元素全是右子樹的結(jié)點(diǎn)。先序序列里緊接著的“左子樹長度”那部分又正好是左子樹的先序序列。這樣一來根定了、左右子樹的范圍也定了剩下的問題被縮小成兩個(gè)規(guī)模更小的子問題天然適合遞歸。后序中序同理后序序列的最后一個(gè)元素是根同樣能用中序序列分離左右子樹。所以考研和面試題里最常見的就是這兩種組合。5.2 手推一遍先序ABDGCEF、中序DGB AECF用一道典型題走一遍。設(shè)先序序列為A B D G C E F中序序列為D G B A E C F。第一步先序第一個(gè)元素是 AA是整棵樹的根。在中序里找AA左邊是D G B右邊是E C F所以A的左子樹有3個(gè)結(jié)點(diǎn)右子樹有3個(gè)結(jié)點(diǎn)。第二步處理左子樹。先序序列里A后面的B D G長度是3正好就是左子樹的先序。左子樹先序第一個(gè)元素是BB是左子樹的根。中序D G B里B在最右邊說明B的右子樹為空D和G都在B左邊。再看先序D GD是左子樹的根中序D G里D在G左邊說明D沒有左孩子、右孩子是G。第三步處理右子樹。先序里剩下的C E F是右子樹先序C是右子樹的根。中序E C F里C左邊是E右邊是F所以C的左孩子是E右孩子是F。最終還原出這棵樹A / \ B C / / \ D E F \ G整個(gè)過程不需要畫很多圖只要盯住“先序定根、中序分左右”這兩句話就夠了。我建議你拿另幾組序列自己練一遍重點(diǎn)體會“左子樹長度”這個(gè)橋梁是怎么串聯(lián)兩條序列的。5.3 遞歸代碼實(shí)現(xiàn)還原代碼上Python實(shí)現(xiàn)非常清晰def build_tree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left build_tree(preorder[1:1 idx], inorder[:idx]) root.right build_tree(preorder[1 idx:], inorder[idx 1:]) return rootidx就是根在中序里的下標(biāo)同時(shí)也是左子樹的結(jié)點(diǎn)數(shù)。所以左子樹的先序是 preorder[1:1idx]左子樹的中序是 inorder[:idx]右子樹的先序是 preorder[1idx:]右子樹的中序是 inorder[idx1:]。這個(gè)切片邊界是寫代碼最容易出錯(cuò)的地方建議對照一個(gè)小例子手動(dòng)試一次寧可慢一點(diǎn)也要把邊界想清楚。后序中序的做法一樣只是根從先序第一個(gè)變成了后序最后一個(gè)。5.4 為什么只有先序和后序不行問答題?？歼@類“為什么”。先序和后序雖然都能定出根但根的孩子是誰、到底是左孩子還是右孩子經(jīng)常說不清。最經(jīng)典的例子先序A B后序B A。單獨(dú)看B它既可以當(dāng)A的左孩子也可以當(dāng)A的右孩子兩顆樹形態(tài)不同但先序和后序序列完全相同。所以僅憑先序后序無法唯一確定一棵二叉樹。這是很關(guān)鍵的一道送分題理解了例子就能答對。6. 從基礎(chǔ)二叉樹延伸搜索樹、平衡樹、線索樹6.1 搜索二叉樹中序有序的查找結(jié)構(gòu)搜索二叉樹BST是一種在普通二叉樹基礎(chǔ)上加了大小約束的結(jié)構(gòu)左子樹所有結(jié)點(diǎn)值都小于根右子樹所有結(jié)點(diǎn)值都大于根。這個(gè)約束帶來了一個(gè)強(qiáng)悍的性質(zhì)——中序遍歷結(jié)果是有序的。寫一句中序代碼BST排出來的就是從小到大。插入邏輯很自然一直到空位就掛上def insert(root, val): if root is None: return TreeNode(val) if val root.val: root.left insert(root.left, val) else: root.right insert(root.right, val) return root查找效率平均是O(log n)但這是建立在樹長得比較均勻的前提下。如果插入序列本身有序比如連續(xù)插入1、2、3、4BST就會退化成一條鏈表查找效率掉到O(n)。這個(gè)退化問題直接催生了平衡樹的需求。刪除操作更麻煩一點(diǎn)分三種情況被刪結(jié)點(diǎn)是葉子直接刪只有一個(gè)孩子把孩子頂上有兩個(gè)孩子可以用右子樹的最小結(jié)點(diǎn)或者左子樹的最大結(jié)點(diǎn)替代再遞歸刪除那個(gè)替代結(jié)點(diǎn)。面試時(shí)能把三種情況分清楚基本就過關(guān)了。6.2 AVL樹讓樹保持“不高不矮”AVL樹是嚴(yán)格平衡的二叉搜索樹核心指標(biāo)是平衡因子左子樹高度減右子樹高度。AVL要求任意結(jié)點(diǎn)的平衡因子絕對值不能超過1否則就要旋轉(zhuǎn)調(diào)整。調(diào)整有四種基本形態(tài)LL型、RR型、LR型、RL型。LL型是左子樹的左子樹過高往右旋轉(zhuǎn)一次解決RR型是右子樹的右子樹過高往左旋轉(zhuǎn)一次LR型是左子樹的右子樹過高需要先左旋再右旋RL型是右子樹的左子樹過高需要先右旋再左旋。不要死背旋轉(zhuǎn)方向我的理解方式是“把冒頭的那個(gè)結(jié)點(diǎn)拎起來讓中間值坐上去”。畫圖推幾次就知道旋轉(zhuǎn)本質(zhì)是把失衡的那條路徑掰回中間位置。AVL樹保證了樹高嚴(yán)格在O(log n)級別所以查找、插入、刪除最壞都是O(log n)代價(jià)是插入刪除時(shí)旋轉(zhuǎn)操作本身也有額外開銷。嵌入式、操作系統(tǒng)這些對穩(wěn)定性敏感的場景里AVL的嚴(yán)格平衡有時(shí)候比紅黑樹的寬松平衡更合適這也是熱搜詞里出現(xiàn)“嵌入式 二叉樹之a(chǎn)vl樹”的原因。6.3 線索二叉樹把空指針變廢為寶前面提到過n個(gè)結(jié)點(diǎn)的二叉鏈表里有n1個(gè)空指針域資源閑置太可惜。線索二叉樹就是在這上面做文章如果左孩子指針為空就讓它指向按某種遍歷順序得到的前驅(qū)結(jié)點(diǎn)如果右孩子指針為空就讓它指向后繼結(jié)點(diǎn)。為了區(qū)分指針到底指向孩子還是線索每個(gè)結(jié)點(diǎn)需要額外增加兩個(gè)標(biāo)志位常用的是 ltag 和 rtag0表示孩子1表示線索。中序線索二叉樹用得最多因?yàn)橹行蛐蛄斜旧砭褪前褬洹袄薄背捎行蛐蛄芯€索化之后就可以像遍歷鏈表一樣順序訪問所有結(jié)點(diǎn)不用遞歸也不用棧。這在頻繁需要找前驅(qū)后繼的場景里比如某些文本編輯器、索引結(jié)構(gòu)很有價(jià)值。線索化過程本質(zhì)上還是中序遍歷只是在訪問結(jié)點(diǎn)時(shí)要額外判斷左右孩子為空并掛上線索?？荚囶}常考“給一棵樹畫出它的中序線索二叉樹”思路是先寫中序序列再找出每個(gè)空指針指向前驅(qū)還是后繼畫起來就不亂了。7. 常見題型與避坑經(jīng)驗(yàn)7.1 高頻考點(diǎn)速查表我把復(fù)習(xí)時(shí)最常遇到的題型按“題目問什么-核心思路-出現(xiàn)場景”整理了一下考查點(diǎn)核心思路?？紙鼍翱罩羔樣驍?shù)量n個(gè)結(jié)點(diǎn)空指針域n1選擇題、填空題葉子數(shù)與度為2的關(guān)系n0 n2 1選擇題、判斷題求深度遞歸max(左,右)1層序按層計(jì)數(shù)大題、機(jī)試已知先序中序還原樹先序定根中序分左右遞歸分治大題、面試手撕三種遍歷序列互推找根、定左右、切長度選擇、簡答判斷完全二叉樹層序出現(xiàn)空結(jié)點(diǎn)后不能再有非空結(jié)點(diǎn)選擇、面試判斷平衡二叉樹后序遍歷邊求高度邊截?cái)嗝嬖嚒?08線索二叉樹找前驅(qū)后繼根據(jù)ltag/rtag判斷直接指還是回退選擇、大題這表不是用來背的是用來做自檢的?？吹侥骋恍心茏约赫f出思路并寫出核心代碼這章才算過關(guān)。7.2 遞歸理解與調(diào)試建議很多人遞歸寫不對不是不會寫函數(shù)而是老想“在腦子里完整跑完遞歸”。我建議改用“黑盒思路”假設(shè)遞歸函數(shù)已經(jīng)能正確解決子問題只關(guān)注當(dāng)前層要拼什么最后把終止條件寫對。如果真的跑不通就在遞歸函數(shù)里加打印把當(dāng)前結(jié)點(diǎn)的值、調(diào)用前的狀態(tài)打出來。比如在preorder開頭加一句print(fenter: {root.val})結(jié)束前加一句print(fleave: {root.val})一跑就能看到完整的調(diào)用軌跡。這種調(diào)試方式對理解遞歸的壓棧、彈棧過程幫助極大。還有一個(gè)小技巧遞歸函數(shù)的返回值不要憋著不接。像求深度、還原二叉樹這些場景遞歸調(diào)用的結(jié)果要返回給上一層很多人漏寫return或者忘接返回值導(dǎo)致結(jié)果永遠(yuǎn)是“致命傷”。寫完代碼先拿最小例子推一遍比如只有一個(gè)根的樹確認(rèn)返回值能正確出來再往上加復(fù)雜場景。7.3 我踩過的幾個(gè)坑第一個(gè)坑是深度起點(diǎn)二義性。我復(fù)習(xí)時(shí)用兩本教材一本根深度記為0另一本記為1結(jié)果同一道題答案不一樣。后來我養(yǎng)成習(xí)慣做題先找題干有沒有“根在第1層”的字樣沒有就默認(rèn)按1面試時(shí)直接問面試官“根節(jié)點(diǎn)深度按1算還是按0算”通常不會被扣分反而顯得嚴(yán)謹(jǐn)。第二個(gè)坑是還原二叉樹時(shí)切分序列的邊界。第一次手寫 build_tree 這類代碼時(shí)我在切片上反復(fù)試錯(cuò)最后總結(jié)出一句話“先序跳過一個(gè)根取前idx個(gè)就是左子樹”。現(xiàn)在寫代碼都是先在草稿紙列出兩個(gè)序列把根的位置畫出來再寫切片公式寫完基本一次過。第三個(gè)坑是判斷完全二叉樹想當(dāng)然。有人覺得“只要某個(gè)結(jié)點(diǎn)沒有左孩子它就不能有右孩子”就夠了這是不嚴(yán)謹(jǐn)?shù)摹８孔V的做法是層序遍歷遇到空結(jié)點(diǎn)后如果后面還能出現(xiàn)非空結(jié)點(diǎn)就不是完全二叉樹。否則就是。我在好幾個(gè)模擬題里靠這個(gè)判斷模板救回來了你們也可以直接用。我自己剛學(xué)二叉樹那會兒最大的體會就是一定要拿著紙筆把遞歸調(diào)用棧畫一遍尤其是中序非遞歸那一路向左的過程。畫完一遍很多題不用背也能寫出來。這篇就寫到這里希望這些經(jīng)驗(yàn)?zāi)茏屇闵僮唿c(diǎn)彎路。