1. 從“遍歷”說(shuō)起為什么二叉樹(shù)的操作離不開(kāi)它如果你剛開(kāi)始接觸數(shù)據(jù)結(jié)構(gòu)或者正在準(zhǔn)備技術(shù)面試那么“二叉樹(shù)”這個(gè)詞你肯定不陌生。而提到二叉樹(shù)幾乎繞不開(kāi)的就是它的“遍歷”。你可能已經(jīng)看過(guò)很多定義前序遍歷、中序遍歷、后序遍歷。但你是否想過(guò)為什么我們要如此執(zhí)著于研究這幾種遍歷方式它們到底解決了什么問(wèn)題簡(jiǎn)單來(lái)說(shuō)遍歷就是系統(tǒng)地訪問(wèn)樹(shù)中每一個(gè)節(jié)點(diǎn)并且每個(gè)節(jié)點(diǎn)只訪問(wèn)一次的過(guò)程。這聽(tīng)起來(lái)很簡(jiǎn)單但卻是二叉樹(shù)幾乎所有高級(jí)操作的基礎(chǔ)。想象一下你要在一棵家族樹(shù)里統(tǒng)計(jì)總?cè)藬?shù)或者在一棵文件系統(tǒng)樹(shù)里搜索某個(gè)特定文件又或者在一棵表達(dá)式樹(shù)里計(jì)算整個(gè)表達(dá)式的值這些操作的第一步都是“走遍”這棵樹(shù)。而“怎么走”——也就是遍歷的順序——直接決定了你訪問(wèn)和處理數(shù)據(jù)的邏輯。前、中、后序遍歷就是三種最經(jīng)典、最基礎(chǔ)的“走法”。它們之所以重要不僅僅是因?yàn)槊嬖嚦？几且驗(yàn)樗鼈冊(cè)诮鉀Q實(shí)際問(wèn)題時(shí)各有妙用。比如前序遍歷天然適合復(fù)制一棵樹(shù)的結(jié)構(gòu)中序遍歷對(duì)于二叉搜索樹(shù)來(lái)說(shuō)能按升序輸出所有節(jié)點(diǎn)后序遍歷則在釋放樹(shù)的內(nèi)存或計(jì)算目錄大小等場(chǎng)景下非常高效。很多人剛開(kāi)始學(xué)的時(shí)候容易把這三種遍歷的順序搞混或者只能死記硬背。這篇內(nèi)容我們就來(lái)徹底拆解這三種遍歷。我不會(huì)只給你干巴巴的遞歸代碼而是會(huì)帶你理解每一種遍歷的核心視角和實(shí)際應(yīng)用場(chǎng)景并給出遞歸與非遞歸迭代兩種實(shí)現(xiàn)方式。更重要的是我會(huì)分享在真正編碼和面試中如何清晰無(wú)誤地推導(dǎo)出遍歷順序以及那些容易踩坑的細(xì)節(jié)。無(wú)論你是初學(xué)者想打牢基礎(chǔ)還是面試者想鞏固要點(diǎn)相信這篇內(nèi)容都能給你帶來(lái)實(shí)實(shí)在在的幫助。2. 理解三種遍歷核心差異在于“根”的位置在深入代碼之前我們必須從本質(zhì)上理解這三種遍歷命名的由來(lái)和它們之間的區(qū)別。這能幫你擺脫死記硬背真正掌握其邏輯。這三種遍歷的名稱——前序Pre-order、中序In-order、后序Post-order——其實(shí)描述的是在訪問(wèn)一個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)時(shí)何時(shí)訪問(wèn)這個(gè)節(jié)點(diǎn)本身根節(jié)點(diǎn)。我們可以把一個(gè)節(jié)點(diǎn)的訪問(wèn)操作記作VVisit處理左子樹(shù)記作L處理右子樹(shù)記作R。那么前序遍歷 (Pre-order):V - L - R。先訪問(wèn)根節(jié)點(diǎn)然后處理左子樹(shù)最后處理右子樹(shù)。“前”意味著“根”在“前”。中序遍歷 (In-order):L - V - R。先處理左子樹(shù)然后訪問(wèn)根節(jié)點(diǎn)最后處理右子樹(shù)。“中”意味著“根”在“中間”。后序遍歷 (Post-order):L - R - V。先處理左子樹(shù)然后處理右子樹(shù)最后訪問(wèn)根節(jié)點(diǎn)。“后”意味著“根”在“最后”。這個(gè)VLR的順序是核心。為了讓你有更直觀的感受我們來(lái)看一棵簡(jiǎn)單的二叉樹(shù)A / \ B C / \ \ D E F對(duì)于這棵樹(shù)前序遍歷A - B - D - E - C - F從根A開(kāi)始V然后遍歷左子樹(shù)以B為根的樹(shù)最后遍歷右子樹(shù)以C為根的樹(shù)。遍歷左子樹(shù)時(shí)同樣遵循VLR訪問(wèn)BV遍歷B的左子樹(shù)D遍歷B的右子樹(shù)E。中序遍歷D - B - E - A - C - F先遍歷A的左子樹(shù)以B為根的樹(shù)然后訪問(wèn)AV最后遍歷A的右子樹(shù)以C為根的樹(shù)。遍歷左子樹(shù)時(shí)遵循LVR先遍歷B的左子樹(shù)D訪問(wèn)BV再遍歷B的右子樹(shù)E。后序遍歷D - E - B - F - C - A先遍歷A的左子樹(shù)以B為根的樹(shù)然后遍歷A的右子樹(shù)以C為根的樹(shù)最后訪問(wèn)AV。遍歷左子樹(shù)時(shí)遵循LRV先遍歷B的左子樹(shù)D再遍歷B的右子樹(shù)E最后訪問(wèn)BV。注意這里說(shuō)的“處理左/右子樹(shù)”指的是遞歸地以同樣的遍歷規(guī)則去訪問(wèn)那棵子樹(shù)。理解這個(gè)遞歸過(guò)程是掌握遍歷的關(guān)鍵。2.1 一個(gè)幫你永不記混的“可視化”技巧我剛開(kāi)始學(xué)的時(shí)候也總記混。后來(lái)我發(fā)現(xiàn)一個(gè)非常有效的技巧在腦子里“走”過(guò)節(jié)點(diǎn)時(shí)想象自己站在每個(gè)節(jié)點(diǎn)上并且把每個(gè)節(jié)點(diǎn)“路過(guò)”三次。第一次路過(guò)從父節(jié)點(diǎn)過(guò)來(lái)準(zhǔn)備進(jìn)入左子樹(shù)。此時(shí)如果執(zhí)行訪問(wèn)操作就是前序。第二次路過(guò)從左子樹(shù)返回準(zhǔn)備進(jìn)入右子樹(shù)。此時(shí)如果執(zhí)行訪問(wèn)操作就是中序。第三次路過(guò)從右子樹(shù)返回準(zhǔn)備回到父節(jié)點(diǎn)。此時(shí)如果執(zhí)行訪問(wèn)操作就是后序。對(duì)于上面樹(shù)的節(jié)點(diǎn)A前序訪問(wèn)A發(fā)生在第一次“路過(guò)”A時(shí)從虛擬的根上來(lái)。中序訪問(wèn)A發(fā)生在從左子樹(shù)(B, D, E)返回后即將進(jìn)入右子樹(shù)(C, F)時(shí)。后序訪問(wèn)A發(fā)生在從右子樹(shù)(C, F)返回后即將回到虛擬的根時(shí)。這個(gè)技巧能幫你從遞歸調(diào)用的堆棧角度理解訪問(wèn)時(shí)機(jī)對(duì)于后續(xù)理解非遞歸實(shí)現(xiàn)也大有裨益。3. 遞歸實(shí)現(xiàn)最直觀的表達(dá)方式遞歸實(shí)現(xiàn)是描述樹(shù)遍歷最自然、最簡(jiǎn)潔的方式因?yàn)樗苯訉?duì)應(yīng)了樹(shù)的遞歸定義一棵樹(shù)由根節(jié)點(diǎn)、左子樹(shù)和右子樹(shù)構(gòu)成。我們先定義一個(gè)簡(jiǎn)單的二叉樹(shù)節(jié)點(diǎn)類這是所有后續(xù)代碼的基礎(chǔ)。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right3.1 前序遍歷的遞歸實(shí)現(xiàn)前序遍歷的順序是VLR。遞歸函數(shù)preorderTraversal接收一個(gè)根節(jié)點(diǎn)root。如果節(jié)點(diǎn)為空直接返回遞歸基。否則執(zhí)行以下三步訪問(wèn)當(dāng)前節(jié)點(diǎn)例如將節(jié)點(diǎn)值加入結(jié)果列表。遞歸遍歷左子樹(shù)。遞歸遍歷右子樹(shù)。def preorderTraversal(root: TreeNode): result [] def dfs(node): if not node: return # 訪問(wèn)根節(jié)點(diǎn) result.append(node.val) # 遍歷左子樹(shù) dfs(node.left) # 遍歷右子樹(shù) dfs(node.right) dfs(root) return result為什么這樣寫(xiě)代碼結(jié)構(gòu)完美對(duì)應(yīng)了V-L-R的定義。dfs(node.left)和dfs(node.right)的調(diào)用意味著“我相信這個(gè)函數(shù)能正確遍歷完左/右子樹(shù)我只需要在它們之前、之后做我該做的事訪問(wèn)當(dāng)前節(jié)點(diǎn)”。這是遞歸思想的精髓相信函數(shù)能完成子任務(wù)。3.2 中序遍歷的遞歸實(shí)現(xiàn)中序遍歷的順序是LVR。遞歸遍歷左子樹(shù)。訪問(wèn)當(dāng)前節(jié)點(diǎn)。遞歸遍歷右子樹(shù)。def inorderTraversal(root: TreeNode): result [] def dfs(node): if not node: return # 遍歷左子樹(shù) dfs(node.left) # 訪問(wèn)根節(jié)點(diǎn) result.append(node.val) # 遍歷右子樹(shù) dfs(node.right) dfs(root) return result特別注意對(duì)于二叉搜索樹(shù)BST中序遍歷的結(jié)果是一個(gè)升序數(shù)組。這是BST一個(gè)極其重要的性質(zhì)常用于驗(yàn)證BST的合法性、在BST中尋找第K小的元素等場(chǎng)景。如果你中序遍歷BST得不到升序序列那這棵樹(shù)肯定不是BST。3.3 后序遍歷的遞歸實(shí)現(xiàn)后序遍歷的順序是LRV。遞歸遍歷左子樹(shù)。遞歸遍歷右子樹(shù)。訪問(wèn)當(dāng)前節(jié)點(diǎn)。def postorderTraversal(root: TreeNode): result [] def dfs(node): if not node: return # 遍歷左子樹(shù) dfs(node.left) # 遍歷右子樹(shù) dfs(node.right) # 訪問(wèn)根節(jié)點(diǎn) result.append(node.val) dfs(root) return result后序遍歷的一個(gè)典型應(yīng)用計(jì)算二叉樹(shù)的高度深度。樹(shù)的高度 1 max(左子樹(shù)高度 右子樹(shù)高度)。你必須先知道左右子樹(shù)的高度才能計(jì)算當(dāng)前節(jié)點(diǎn)的高度這正是一個(gè)后序遍歷的過(guò)程。def maxDepth(root: TreeNode) - int: if not root: return 0 left_depth maxDepth(root.left) # 遍歷左子樹(shù) right_depth maxDepth(root.right) # 遍歷右子樹(shù) return max(left_depth, right_depth) 1 # 訪問(wèn)根節(jié)點(diǎn)計(jì)算高度3.4 遞歸實(shí)現(xiàn)的優(yōu)缺點(diǎn)與注意事項(xiàng)優(yōu)點(diǎn)代碼簡(jiǎn)潔邏輯清晰幾乎是對(duì)遍歷定義的直接翻譯。易于理解非常適合教學(xué)和快速原型實(shí)現(xiàn)。缺點(diǎn)與坑點(diǎn)棧溢出風(fēng)險(xiǎn)對(duì)于深度非常大的樹(shù)例如退化成鏈表的樹(shù)遞歸層級(jí)過(guò)深可能導(dǎo)致調(diào)用棧溢出。這是遞歸方法的固有缺陷。結(jié)果傳遞注意上面代碼中我們使用了一個(gè)外層列表result和一個(gè)內(nèi)層遞歸函數(shù)dfs。result作為閉包變量被內(nèi)層函數(shù)修改。這是一種常見(jiàn)且清晰的寫(xiě)法。你也可以選擇將result作為參數(shù)在遞歸函數(shù)中傳遞但那樣代碼會(huì)稍顯冗余。空節(jié)點(diǎn)判斷遞歸基if not node: return至關(guān)重要。它確保了遞歸能在葉子節(jié)點(diǎn)處正確終止而不會(huì)對(duì)None調(diào)用.left或.right屬性導(dǎo)致錯(cuò)誤。實(shí)操心得在面試中如果你被要求寫(xiě)遍歷先寫(xiě)出遞歸版本通常是穩(wěn)妥且快速的。這展示了你對(duì)問(wèn)題本質(zhì)的理解。但最好能主動(dòng)提及“遞歸版本可能存在棧溢出問(wèn)題也可以用迭代棧的方式實(shí)現(xiàn)”這能體現(xiàn)你的知識(shí)廣度。4. 迭代實(shí)現(xiàn)用棧模擬遞歸過(guò)程遞歸的本質(zhì)是函數(shù)調(diào)用棧。因此所有遞歸算法都可以用棧Stack這種數(shù)據(jù)結(jié)構(gòu)來(lái)模擬實(shí)現(xiàn)迭代版本。迭代版本沒(méi)有棧溢出的風(fēng)險(xiǎn)但邏輯上通常比遞歸版本更復(fù)雜一些。理解迭代實(shí)現(xiàn)能讓你對(duì)遍歷過(guò)程有更深刻的把握。我們需要顯式地使用一個(gè)棧來(lái)存儲(chǔ)待處理的節(jié)點(diǎn)。核心問(wèn)題是節(jié)點(diǎn)入棧和出棧的時(shí)機(jī)以及何時(shí)訪問(wèn)節(jié)點(diǎn)值。4.1 前序遍歷的迭代實(shí)現(xiàn)前序遍歷的迭代是相對(duì)簡(jiǎn)單的。我們遵循VLR的順序。先把根節(jié)點(diǎn)壓入棧。循環(huán)棧不為空彈出棧頂節(jié)點(diǎn)并訪問(wèn)它。因?yàn)闂Ｊ呛筮M(jìn)先出LIFO為了保證訪問(wèn)順序是V-L-R我們需要先將右子節(jié)點(diǎn)壓棧再將左子節(jié)點(diǎn)壓棧。這樣下一次循環(huán)彈出處理的就是左子節(jié)點(diǎn)。def preorderTraversalIterative(root: TreeNode): if not root: return [] result [] stack [root] # 初始化棧放入根節(jié)點(diǎn) while stack: node stack.pop() # 彈出棧頂節(jié)點(diǎn) result.append(node.val) # 訪問(wèn)節(jié)點(diǎn) # 先右后左入棧 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result為什么先右后左這是關(guān)鍵。我們希望接下來(lái)處理左子樹(shù)所以左孩子應(yīng)該后入棧、先彈出。右孩子先入棧、后彈出。這個(gè)順序正好與遞歸調(diào)用dfs(node.left)在dfs(node.right)之前執(zhí)行相反因?yàn)闂７崔D(zhuǎn)了順序。4.2 中序遍歷的迭代實(shí)現(xiàn)中序遍歷LVR的迭代邏輯是三種中最需要技巧的。我們不能像前序那樣在彈出時(shí)訪問(wèn)因?yàn)樵L問(wèn)時(shí)機(jī)在遍歷完左子樹(shù)之后。核心思路使用一個(gè)指針curr來(lái)表示當(dāng)前遍歷到的節(jié)點(diǎn)并用棧來(lái)保存“已經(jīng)路過(guò)但還未訪問(wèn)”的節(jié)點(diǎn)這些節(jié)點(diǎn)可以看作是“遞歸調(diào)用路徑上的父節(jié)點(diǎn)”。從根節(jié)點(diǎn)開(kāi)始curr指向當(dāng)前節(jié)點(diǎn)。循環(huán)curr不為空或棧不為空如果curr不為空一直向左走將沿途節(jié)點(diǎn)壓入棧中curr curr.left。這模擬了遞歸深入左子樹(shù)的過(guò)程。如果curr為空意味著已經(jīng)到達(dá)某條左路徑的盡頭。此時(shí)從棧中彈出一個(gè)節(jié)點(diǎn)這是最近一個(gè)未訪問(wèn)的“根”節(jié)點(diǎn)訪問(wèn)它。然后讓curr指向該節(jié)點(diǎn)的右子節(jié)點(diǎn)開(kāi)始處理右子樹(shù)。def inorderTraversalIterative(root: TreeNode): result [] stack [] curr root while curr or stack: # 模擬遞歸深入左子樹(shù) while curr: stack.append(curr) curr curr.left # 左子樹(shù)到頭彈出“根”節(jié)點(diǎn)并訪問(wèn) curr stack.pop() result.append(curr.val) # 轉(zhuǎn)向右子樹(shù) curr curr.right return result這個(gè)算法非常精妙。外層while條件curr or stack確保了只要還有節(jié)點(diǎn)待處理就繼續(xù)。內(nèi)層的while curr完成了“深入左子樹(shù)” (L)。stack.pop()和result.append完成了“訪問(wèn)根” (V)。curr curr.right則開(kāi)啟了“遍歷右子樹(shù)” (R) 的新一輪循環(huán)。4.3 后序遍歷的迭代實(shí)現(xiàn)后序遍歷LRV的迭代實(shí)現(xiàn)也有多種方法其中一種巧妙的方法是利用前序遍歷的變種。我們知道前序是VLR后序是LRV。如果我們能實(shí)現(xiàn)一種VRL的遍歷然后將結(jié)果反轉(zhuǎn)不就得到LRV了嗎因?yàn)?VRL)的逆序 LRV。如何實(shí)現(xiàn)VRL很簡(jiǎn)單模仿前序遍歷但是調(diào)換左右子節(jié)點(diǎn)的入棧順序改為先左后右。def postorderTraversalIterative(root: TreeNode): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 訪問(wèn)節(jié)點(diǎn) # 注意這里是先左后右 if node.left: stack.append(node.left) if node.right: stack.append(node.right) # 最后將結(jié)果反轉(zhuǎn) return result[::-1]這個(gè)方法非常取巧代碼簡(jiǎn)潔。但它的缺點(diǎn)是需要額外的空間來(lái)存儲(chǔ)整個(gè)結(jié)果列表用于反轉(zhuǎn)并且訪問(wèn)節(jié)點(diǎn)的順序與真正的后序邏輯不同可能不利于在遍歷過(guò)程中進(jìn)行某些即時(shí)操作。更符合邏輯的迭代后序遍歷需要一個(gè)指針來(lái)記錄上一個(gè)訪問(wèn)的節(jié)點(diǎn)以判斷當(dāng)前節(jié)點(diǎn)的右子樹(shù)是否已被訪問(wèn)過(guò)。邏輯更復(fù)雜但空間效率更高不需要存儲(chǔ)完整結(jié)果再反轉(zhuǎn)。這里也給出實(shí)現(xiàn)供你對(duì)比理解def postorderTraversalIterative2(root: TreeNode): if not root: return [] result [] stack [] prev None # 記錄前一個(gè)訪問(wèn)的節(jié)點(diǎn) curr root while curr or stack: # 深入左子樹(shù) while curr: stack.append(curr) curr curr.left # 查看棧頂節(jié)點(diǎn) curr stack[-1] # 如果右子樹(shù)不存在或已被訪問(wèn)則訪問(wèn)當(dāng)前節(jié)點(diǎn) if not curr.right or curr.right prev: stack.pop() result.append(curr.val) prev curr curr None # 當(dāng)前子樹(shù)處理完畢強(qiáng)制彈出棧中下一個(gè) else: # 否則轉(zhuǎn)向右子樹(shù) curr curr.right return result這個(gè)版本中prev變量是關(guān)鍵。當(dāng)從棧頂取出一個(gè)節(jié)點(diǎn)時(shí)如果它的右子節(jié)點(diǎn)為空或者右子節(jié)點(diǎn)剛剛被訪問(wèn)過(guò)prev說(shuō)明它的左右子樹(shù)都已處理完畢可以訪問(wèn)它自己了。避坑指南在面試或?qū)嶋H編碼中如果你被要求寫(xiě)迭代后序我推薦先寫(xiě)“前序變種反轉(zhuǎn)”的方法因?yàn)樗蝗菀壮鲥e(cuò)并且可以快速解釋思路。如果面試官追問(wèn)更高效或更正統(tǒng)的方法再闡述prev指針的方法。同時(shí)要能說(shuō)清楚兩種方法的時(shí)空復(fù)雜度都是 O(n)和差異。5. 層序遍歷另一種重要的遍歷維度雖然標(biāo)題聚焦于前中后序但“層序遍歷”作為熱詞被頻繁提及它同樣至關(guān)重要且實(shí)現(xiàn)思路完全不同。前中后序?qū)儆谏疃葍?yōu)先搜索DFS而層序遍歷屬于廣度優(yōu)先搜索BFS。層序遍歷按樹(shù)的層級(jí)從上到下、從左到右訪問(wèn)節(jié)點(diǎn)。它的實(shí)現(xiàn)通常借助隊(duì)列Queue。from collections import deque def levelOrder(root: TreeNode): if not root: return [] result [] queue deque([root]) # 使用雙端隊(duì)列模擬隊(duì)列從左側(cè)彈出 while queue: level_size len(queue) current_level [] for _ in range(level_size): # 處理當(dāng)前層的所有節(jié)點(diǎn) node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result為什么用隊(duì)列隊(duì)列先進(jìn)先出FIFO的特性保證了我們先訪問(wèn)上一層的節(jié)點(diǎn)并將它們的子節(jié)點(diǎn)按順序加入隊(duì)尾從而自然實(shí)現(xiàn)了按層遍歷。層序遍歷的應(yīng)用場(chǎng)景非常直觀比如尋找二叉樹(shù)的最大寬度、打印樹(shù)的結(jié)構(gòu)、在二叉樹(shù)中找最短路徑如從根到葉子的最小深度等。6. 核心應(yīng)用場(chǎng)景與常見(jiàn)問(wèn)題剖析理解了怎么遍歷接下來(lái)就要看看它們能用來(lái)干什么。這里結(jié)合熱詞中的“常見(jiàn)問(wèn)題”解析幾個(gè)典型應(yīng)用。6.1 根據(jù)遍歷序列還原二叉樹(shù)這是一個(gè)經(jīng)典問(wèn)題。通常需要中序遍歷序列搭配前序或后序遍歷序列之一才能唯一確定一棵二叉樹(shù)。為什么前序/后序提供了根節(jié)點(diǎn)的信息前序第一個(gè)是根后序最后一個(gè)是根。中序提供了左右子樹(shù)的分界信息根節(jié)點(diǎn)左邊是左子樹(shù)中序右邊是右子樹(shù)中序。以前序中序還原為例前序數(shù)組preorder的第一個(gè)元素preorder[0]是根節(jié)點(diǎn)。在中序數(shù)組inorder中找到這個(gè)根節(jié)點(diǎn)的位置index。inorder中index左邊的部分inorder[:index]是左子樹(shù)的中序序列右邊的部分inorder[index1:]是右子樹(shù)的中序序列。根據(jù)左子樹(shù)中序序列的長(zhǎng)度可以在preorder中劃分出左子樹(shù)的前序序列preorder[1:1len(left_inorder)]和右子樹(shù)的前序序列preorder[1len(left_inorder):]。遞歸地對(duì)左子樹(shù)和右子樹(shù)進(jìn)行步驟1-4。def buildTree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) # 找到根在中序中的位置 root_index_inorder inorder.index(root_val) # 劃分中序序列 left_inorder inorder[:root_index_inorder] right_inorder inorder[root_index_inorder1:] # 劃分前序序列 (關(guān)鍵左子樹(shù)前序長(zhǎng)度等于左子樹(shù)中序長(zhǎng)度) left_preorder preorder[1:1len(left_inorder)] right_preorder preorder[1len(left_inorder):] # 遞歸構(gòu)建 root.left buildTree(left_preorder, left_inorder) root.right buildTree(right_preorder, right_inorder) return root注意上述代碼中inorder.index(root_val)在每次遞歸中時(shí)間復(fù)雜度是 O(n)可以通過(guò)預(yù)先建立“值-索引”的哈希表來(lái)優(yōu)化到 O(1)。這是面試中一個(gè)常見(jiàn)的優(yōu)化點(diǎn)。6.2 二叉搜索樹(shù)BST與中序遍歷正如之前提到的對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷會(huì)得到一個(gè)升序數(shù)組。這是BST的核心性質(zhì)。基于這個(gè)性質(zhì)我們可以解決很多問(wèn)題驗(yàn)證BST中序遍歷二叉樹(shù)檢查遍歷結(jié)果是否嚴(yán)格遞增。BST中第K小的元素中序遍歷記錄訪問(wèn)的節(jié)點(diǎn)個(gè)數(shù)第K個(gè)訪問(wèn)的節(jié)點(diǎn)即為所求。可以通過(guò)迭代中序遍歷提前終止來(lái)優(yōu)化。恢復(fù)錯(cuò)誤的BSTBST中兩個(gè)節(jié)點(diǎn)被意外交換會(huì)導(dǎo)致中序序列中出現(xiàn)兩處“逆序”。找到這兩個(gè)節(jié)點(diǎn)并交換回來(lái)即可。6.3 二叉樹(shù)深度與遍歷求二叉樹(shù)的深度最大深度是后序遍歷的典型應(yīng)用代碼已在3.3節(jié)展示。求二叉樹(shù)的最小深度也可以用BFS層序遍歷更高效地解決遇到第一個(gè)葉子節(jié)點(diǎn)即可返回當(dāng)前深度。6.4 關(guān)于線索二叉樹(shù)線索二叉樹(shù)是一種優(yōu)化存儲(chǔ)結(jié)構(gòu)它利用二叉樹(shù)中的空指針域按照某種遍歷順序前序、中序、后序?qū)⒐?jié)點(diǎn)“線索化”指向其前驅(qū)或后繼節(jié)點(diǎn)。這樣可以實(shí)現(xiàn)不需要棧或遞歸的遍歷。雖然在實(shí)際工程中直接使用較少但它是理解二叉樹(shù)存儲(chǔ)結(jié)構(gòu)和遍歷關(guān)系的一個(gè)很好深化知識(shí)點(diǎn)。其核心思想是在遍歷過(guò)程中如果當(dāng)前節(jié)點(diǎn)的左/右孩子為空則將其指向遍歷順序下的前驅(qū)/后繼節(jié)點(diǎn)并增加一個(gè)標(biāo)志位區(qū)分指針指向的是孩子還是線索。7. 總結(jié)與高階思考遍歷是二叉樹(shù)操作的基石。前、中、后序是深度優(yōu)先思想的體現(xiàn)而層序遍歷是廣度優(yōu)先思想的體現(xiàn)。遞歸實(shí)現(xiàn)簡(jiǎn)潔迭代實(shí)現(xiàn)穩(wěn)健各有適用場(chǎng)景。在實(shí)際開(kāi)發(fā)或面試中關(guān)于遍歷你可能會(huì)遇到以下變體或深入問(wèn)題Morris遍歷一種時(shí)間復(fù)雜度O(n)但空間復(fù)雜度只有O(1)的遍歷算法。它通過(guò)臨時(shí)修改樹(shù)的結(jié)構(gòu)利用葉子節(jié)點(diǎn)的空指針來(lái)實(shí)現(xiàn)遍歷完成后恢復(fù)樹(shù)的結(jié)構(gòu)。這是對(duì)迭代遍歷空間優(yōu)化的極致體現(xiàn)。N叉樹(shù)的遍歷原理相通只是每個(gè)節(jié)點(diǎn)可能有多個(gè)孩子。前序和后序遍歷很容易推廣中序遍歷對(duì)于多叉樹(shù)沒(méi)有普遍定義。迭代遍歷的統(tǒng)一寫(xiě)法有一種巧妙的迭代寫(xiě)法將訪問(wèn)節(jié)點(diǎn)和待處理節(jié)點(diǎn)都?jí)喝霔２⑼ㄟ^(guò)一個(gè)空節(jié)點(diǎn)作為“已訪問(wèn)”的標(biāo)記可以用一套非常相似的代碼框架實(shí)現(xiàn)三種遍歷。這種寫(xiě)法有助于理解和記憶但可能不如專用寫(xiě)法直觀。我個(gè)人在學(xué)習(xí)和教學(xué)過(guò)程中最大的體會(huì)是不要孤立地記憶代碼而要理解每種遍歷對(duì)應(yīng)的“訪問(wèn)時(shí)機(jī)”和“問(wèn)題場(chǎng)景”。當(dāng)你遇到一個(gè)二叉樹(shù)問(wèn)題時(shí)先問(wèn)自己解決這個(gè)問(wèn)題需要在什么時(shí)機(jī)第一次路過(guò)、從左子樹(shù)返回后、從右子樹(shù)返回后、按層訪問(wèn)或處理節(jié)點(diǎn)想清楚了這一點(diǎn)該用哪種遍歷方式以及是遞歸還是迭代實(shí)現(xiàn)就變得一目了然了。最后多動(dòng)手畫(huà)圖。拿一張紙畫(huà)一棵樹(shù)用筆模擬遞歸調(diào)用棧或迭代用的棧/隊(duì)列一步步走完遍歷過(guò)程。這是理解二叉樹(shù)遍歷最有效、最扎實(shí)的方法。