如何做網(wǎng)站模特,鄉(xiāng)下房屋室內(nèi)裝修,紡織行業(yè)網(wǎng)站怎么做吸引人,網(wǎng)站主題編輯工具WordPress二叉樹是數(shù)據(jù)結(jié)構(gòu)中遞歸思想的最佳演練場。很多同學在刷題時#xff0c;往往看答案覺得很簡單#xff0c;自己寫卻無從下手。其實#xff0c;二叉樹的遞歸無非就兩種套路#xff1a;怎么傳下去#xff1f;#xff08;父節(jié)點把要求傳給子節(jié)點#xff0c;如判斷對稱#…二叉樹是數(shù)據(jù)結(jié)構(gòu)中遞歸思想的最佳演練場。很多同學在刷題時往往看答案覺得很簡單自己寫卻無從下手。其實二叉樹的遞歸無非就兩種套路怎么傳下去父節(jié)點把要求傳給子節(jié)點如判斷對稱怎么收上來子節(jié)點把結(jié)果匯報給父節(jié)點如計算直徑今天我們通過兩道經(jīng)典題目LeetCode 101 和 543來徹底搞懂這兩個套路。01. 對稱二叉樹 (Symmetric Tree)題目解析我們要判斷一棵樹是不是軸對稱的。這就好比我們在樹的中間放一面鏡子左邊的樣子和右邊的樣子必須完全重合。核心邏輯鏡像對比很多初學者容易犯的錯誤是直接判斷root-left和root-right是不是“完全相同”的樹。錯對稱不是“相同”而是“鏡像”。我們可以把這棵大樹拆解成無數(shù)個小的“三角單元”。對于任意兩個對稱位置的節(jié)點p左邊那個和q右邊那個如果要滿足對稱必須同時滿足三個條件值相等p的值必須等于q的值。外側(cè)對齊p的左孩子最外側(cè)必須等于q的右孩子最外側(cè)。內(nèi)側(cè)對齊p的右孩子靠近中間必須等于q的左孩子靠近中間。代碼深度拆解C代碼實現(xiàn)class Solution { public: bool isSymmetric(TreeNode* root) { // 根節(jié)點的左子樹和右子樹進行鏡像對比 return isSameTree(root-left, root-right); } // 這里雖然函數(shù)名叫 isSameTree但實際邏輯是 checkMirror // 作用判斷 p 和 q 兩棵樹是否互為鏡像 bool isSameTree(TreeNode* p, TreeNode* q) { // 1. 遞歸終止條件處理空節(jié)點的情況 // 如果兩個都為空說明到底了且匹配返回 true // 如果只有一個為空說明不對稱結(jié)構(gòu)不同返回 false if (p nullptr || q nullptr) return q p; // 2. 核心遞歸邏輯 // 條件A: 當前節(jié)點值必須一樣 // 條件B: p的左邊 VS q的右邊 (外側(cè)互相對比) // 條件C: p的右邊 VS q的左邊 (內(nèi)側(cè)互相對比) return p-val q-val isSameTree(p-left, q-right) isSameTree(p-right, q-left); } };為什么這么寫代碼中最精髓的一句是isSameTree(p-left, q-right) isSameTree(p-right, q-left)。這正是體現(xiàn)了**“鏡像”**的定義。如果你寫成了p-left, q-left那就是判斷兩棵樹是否完全一樣平移而不是對稱了。復雜度分析時間復雜度O(N)。 我們需要遍歷樹中的每一個節(jié)點一次。空間復雜度O(H)其中 H 是樹的高度。 這里的空間消耗主要來自遞歸調(diào)用的?？臻g。在最壞情況下樹退化成鏈表高度為 N最好情況下完全二叉樹高度為 logN。02. 二叉樹的直徑 (Diameter of Binary Tree)題目解析這道題要求的是二叉樹中任意兩個節(jié)點間的最長路徑長度。注意一個大坑這條最長路徑不一定經(jīng)過根節(jié)點。它可能完全存在于左子樹內(nèi)部也可能在右子樹內(nèi)部。核心邏輯后序遍歷 全局打擂臺既然路徑可能出現(xiàn)在任何地方但所有的路徑都有一個共同點它一定有一個“最高點”轉(zhuǎn)折點。 對于任何一個節(jié)點穿過該節(jié)點的最長路徑 左子樹的最大深度右子樹的數(shù)據(jù)深度。所以我們的策略是自底向上后序遍歷先算出子樹的深度再匯報給父節(jié)點。全局打擂在計算深度的過程中順便計算“經(jīng)過當前節(jié)點的最長路徑”并用一個全局變量ans記錄歷史最大值。代碼深度拆解C代碼實現(xiàn)class Solution { // 全局變量維護最大直徑 // 因為最長路徑可能不經(jīng)過根節(jié)點所以需要在遍歷過程中實時更新最大值 int ans 0; // 這個函數(shù)的定義非常關(guān)鍵 // 它的作用是返回以 root 為根的樹的【最大深度】 // 它的副作用是更新經(jīng)過 root 的【最大直徑】 int dfs(TreeNode* root) { // 1. 終止條件空節(jié)點深度為 0 if (root nullptr) return 0; // 2. 遞歸獲取左右子樹的深度自底向上 int left dfs(root-left); int right dfs(root-right); // 3. 【核心邏輯之一更新答案】 // 經(jīng)過當前節(jié)點的最長路徑 左臂長 右臂長 // 這是一條穿過當前節(jié)點的路徑類似倒V字型 ans max(ans, left right); // 4. 【核心邏輯之二返回深度】 // 當前節(jié)點要匯報給父節(jié)點的是我這條分支有多長 // 我只能選左邊或右邊更長的一條路繼續(xù)往上延伸不能兩條都選那樣就分叉了 // 所以返回 max(left, right) 1 (加1是加上當前節(jié)點自己) return max(left, right) 1; } public: int diameterOfBinaryTree(TreeNode* root) { dfs(root); return ans; } };為什么這么寫很多同學搞混淆的地方在于為什么更新ans用加法而返回值用max更新ans我們在找直徑路徑長度。一條路徑穿過當前節(jié)點是把左腿和右腿連起來所以是left right。返回值我們在算深度高度。對于父節(jié)點來說當前節(jié)點只是它的一條“腿”。一條路徑不能分叉只能選最長的那條腿往上走所以是max(left, right) 1。復雜度分析時間復雜度O(N)。 每個節(jié)點被訪問一次計算深度是 O(1) 的操作?？臻g復雜度O(H)。 同樣取決于遞歸棧的深度。最壞情況 O(N)平均情況 O(logN)。總結(jié)這兩道題雖然都是遞歸但方向截然不同對稱二叉樹是帶著任務(wù)往下跑拿著左邊的節(jié)點去和右邊匹配這是一種自頂向下的邏輯。二叉樹直徑是帶著結(jié)果往上報子節(jié)點算好了深度匯報給父節(jié)點父節(jié)點順便計算一下經(jīng)過自己的最長路徑這是一種自底向上的邏輯。掌握了這兩種思維你對二叉樹的遞歸理解就上了一個臺階