簡述上課網(wǎng)站建設所用的技術架構,建站管理過程,做招聘網(wǎng)站怎么設計框架,h5網(wǎng)頁制作代碼二叉樹的遍歷是樹形結構中最基礎的操作。所謂的**“前序遍歷”**#xff0c;其實是指“根節(jié)點”相對于左右子樹的訪問順序。 1. 記住口訣#xff1a;根 - 左 - 右 前序遍歷#xff08;Pre-order Traversal#xff09;的邏輯非常固定#xff1a; 首先訪問 根節(jié)點…二叉樹的遍歷是樹形結構中最基礎的操作。所謂的**“前序遍歷”**其實是指“根節(jié)點”相對于左右子樹的訪問順序。1. 記住口訣根 - 左 - 右前序遍歷Pre-order Traversal的邏輯非常固定首先訪問根節(jié)點 (Root)。然后遞歸地訪問左子樹 (Left)。最后遞歸地訪問右子樹 (Right)。2. 解法一遞歸法最直觀遞歸是最符合樹定義的方法因為樹本身就是遞歸定義的。classSolution:defpreorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node):ifnotnode:return# 1. 根先記錄當前節(jié)點的值res.append(node.val)# 2. 左遞歸遍歷左子樹dfs(node.left)# 3. 右遞歸遍歷右子樹dfs(node.right)dfs(root)returnres3. 解法二迭代法利用棧 Stack在面試中面試官經(jīng)常會問“如果不讓你用遞歸你怎么實現(xiàn)”這時我們需要模擬遞歸的過程。遞歸本質上是利用了系統(tǒng)的調用棧所以我們可以手動維護一個棧 (Stack)。關鍵點棧是“后進先出”的。為了保證“先左后右”的訪問順序我們在壓棧時要先壓右子樹再壓左子樹。classSolution:defpreorderTraversal(self,root:Optional[TreeNode])-List[int]:ifnotroot:return[]stack[root]res[]whilestack:# 彈出棧頂節(jié)點當前的“根”nodestack.pop()res.append(node.val)# 先把右孩子放進去后出ifnode.right:stack.append(node.right)# 再把左孩子放進去先出ifnode.left:stack.append(node.left)returnres4. 總結與對比前序遍歷根 - 左 - 右中序遍歷左 - 根 - 右145 題后序遍歷左 - 右 - 根94 題為什么迭代法里要先壓right因為我們想要先處理left。在棧結構里最后放進去的東西會最先被彈出來。所以先把右邊的“存著”處理完左邊那一條線后再回來處理右邊。復雜度分析時間復雜度O ( n ) O(n)O(n)。每個節(jié)點都被訪問且僅訪問一次。空間復雜度O ( n ) O(n)O(n)。最壞情況下樹呈鏈狀遞歸棧或手動棧的深度會達到n nn。中序遍歷In-order Traversal是二叉樹最常用的遍歷方式之一特別是在**二叉搜索樹BST**中中序遍歷的結果恰好是升序排列的。1. 記住口訣左 - 根 - 右中序遍歷的邏輯順序是首先遞歸地訪問左子樹 (Left)。然后訪問根節(jié)點 (Root)。最后遞歸地訪問右子樹 (Right)。2. 解法一遞歸法極其簡單你只需要在“前序遍歷”的基礎上把記錄值的語句res.append挪到兩次遞歸調用中間即可。classSolution:definorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node):ifnotnode:return# 1. 左一直往左走dfs(node.left)# 2. 根走不動了再記錄當前值res.append(node.val)# 3. 右最后看右邊dfs(node.right)dfs(root)returnres3. 解法二迭代法面試重點迭代法實現(xiàn)中序遍歷比前序遍歷稍微復雜一點因為訪問節(jié)點的順序和處理節(jié)點的順序是不一致的。我們需要先“潛入”到最左端的葉子節(jié)點。邏輯一路向左只要當前節(jié)點不為空就把它壓入棧并繼續(xù)往左走。彈出并記錄左邊走到底了從棧中彈出一個節(jié)點這就是當前的“根”記錄它的值。轉向右邊處理完根節(jié)點后把指針指向它的右孩子重復上述過程。classSolution:definorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]stack[]currroot# curr 不為空或者棧不為空就繼續(xù)whilecurrorstack:# 步驟 1一路向左扎到底whilecurr:stack.append(curr)currcurr.left# 步驟 2彈出棧頂元素最左或最近的根currstack.pop()res.append(curr.val)# 步驟 3轉向右子樹currcurr.rightreturnres4. 為什么中序遍歷很重要排序屬性如果你對一棵“二叉搜索樹”進行中序遍歷得到的結果一定是從小到大排好序的數(shù)組。驗證搜索樹判斷一棵樹是否是二叉搜索樹LeetCode 98最簡單的方法就是看它的中序遍歷是否是遞增的?？偨Y三種遍歷的遞歸區(qū)別前序記錄- 左 - 右先看到根再看子樹中序左 -記錄- 右先看完左邊回頭看根再看右邊后序左 - 右 -記錄最后才看根常用于計算樹的高度或刪除樹后序遍歷Post-order Traversal是三種遍歷中最“內斂”的一種。它的特點是必須等左右子樹全部處理完才處理根節(jié)點。1. 記住口訣左 - 右 - 根后序遍歷的邏輯順序是首先遞歸地訪問左子樹 (Left)。然后遞歸地訪問右子樹 (Right)。最后訪問根節(jié)點 (Root)。2. 解法一遞歸法依然是那三行核心代碼只是順序變了。它是計算樹的高度104題或刪除整棵樹時的標準做法。classSolution:defpostorderTraversal(self,root:Optional[TreeNode])-List[int]:res[]defdfs(node):ifnotnode:returndfs(node.left)# 1. 左dfs(node.right)# 2. 右res.append(node.val)# 3. 根dfs(root)returnres3. 解法二迭代法“偷懶”鏡像反轉法后序遍歷的迭代法如果正著寫非常復雜因為你需要判斷右子樹是否已經(jīng)訪問過。但有一個神級腦筋急轉彎前序遍歷是根 - 左 - 右如果我們稍微改下順序寫成根 - 右 - 左把這個結果整體反轉 (Reverse)就會得到左 - 右 - 根——這正是后序遍歷classSolution:defpostorderTraversal(self,root:Optional[TreeNode])-List[int]:ifnotroot:return[]stack[root]res[]# 按照 根 - 右 - 左 的順序入棧whilestack:nodestack.pop()res.append(node.val)# 因為是棧先壓左后壓右彈出來的就是先右后左ifnode.left:stack.append(node.left)ifnode.right:stack.append(node.right)# 最后把 [根, 右, 左] 反轉成 [左, 右, 根]returnres[::-1]4. 為什么后序遍歷很有用后序遍歷體現(xiàn)了**“自底向上”**的思想。計算樹的高度你需要知道左子樹多高右子樹多高然后取最大值加 1根節(jié)點。計算子樹節(jié)點和你必須先算出左右兩邊的和才能算出包含當前根的總和。最近公共祖先 (LCA)通過后序遍歷向上回溯信息。三種遍歷的直觀總結想象一棵樹你拿著一支筆沿著樹的外圍輪廓走一圈從根左側出發(fā)繞一圈回到根右側前序遍歷在經(jīng)過節(jié)點的左側時記錄它。中序遍歷在經(jīng)過節(jié)點的底部時記錄它。后序遍歷在經(jīng)過節(jié)點的右側時記錄它。知識點大串聯(lián)到目前為止我們已經(jīng)橫跨了三個大領域線性結構鏈表雙指針、快慢指針、數(shù)組滑動窗口、原地翻轉。數(shù)學模擬大數(shù)加法進位處理、補零邏輯。樹形結構二叉樹前中后序遞歸與迭代。發(fā)現(xiàn)**“棧 (Stack)”和“遞歸”**其實是雙胞胎層序遍歷Level-order Traversal與之前的前、中、后序遍歷完全不同。前三種屬于深度優(yōu)先遍歷DFS而層序遍歷屬于廣度優(yōu)先遍歷BFS。它像剝洋蔥一樣從根節(jié)點開始一層一層地由上到下、由左到右訪問所有節(jié)點。1. 核心工具隊列Queue實現(xiàn)層序遍歷的關鍵在于使用“隊列”這種先進先出FIFO的數(shù)據(jù)結構入隊把根節(jié)點放進隊列。循環(huán)只要隊列不為空記錄當前層的節(jié)點個數(shù)確定這層有多少人。依次彈出這些節(jié)點。把它們的左、右孩子如果有依次加入隊列末尾。2. 代碼實現(xiàn) (Python)fromcollectionsimportdequeclassSolution:deflevelOrder(self,root:Optional[TreeNode])-List[List[int]]:ifnotroot:return[]res[]# 使用 deque雙端隊列popleft() 的時間復雜度為 O(1)queuedeque([root])whilequeue:# 1. 確定當前層有多少個節(jié)點level_sizelen(queue)current_level[]# 2. 連續(xù)處理 level_size 個節(jié)點保證它們屬于同一層for_inrange(level_size):nodequeue.popleft()current_level.append(node.val)# 3. 將下一層的孩子節(jié)點加入隊列ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)# 4. 將這一層的結果加入大列表res.append(current_level)returnres3. 為什么需要level_size len(queue)這是層序遍歷最關鍵的一步。因為隊列在不斷地添加新節(jié)點下一層的孩子如果不提前固定當前層的數(shù)量while循環(huán)就會一直跑下去你無法區(qū)分哪些節(jié)點屬于第一層哪些屬于第二層。通過len(queue)我們給當前層畫了一個“圈”保證for循環(huán)只處理這一層的節(jié)點。4. 復雜度分析時間復雜度O ( N ) O(N)O(N)。每個節(jié)點入隊和出隊各一次。空間復雜度O ( N ) O(N)O(N)。在最壞情況下比如滿二叉樹最后一層的節(jié)點數(shù)大約是N / 2 N/2N/2隊列需要存儲這些節(jié)點。5. 常見變形題層序遍歷的模版非常強大稍微改動就能解決很多問題二叉樹的最大深度層序遍歷跑了多少個while循環(huán)深度就是多少。二叉樹的右視圖每一層for循環(huán)結束時的最后一個節(jié)點就是從右邊看到的節(jié)點。之字形遍歷根據(jù)層數(shù)的奇偶性反轉current_level列表?？偨YDFS vs BFS特性DFS (前中后序)BFS (層序)數(shù)據(jù)結構棧 (Stack) / 遞歸隊列 (Queue)特點一條路走到黑再回溯穩(wěn)扎穩(wěn)打層層推進適用場景路徑搜索、找祖先、樹結構更改最短路徑、層級統(tǒng)計