認識遞歸

1. 遞歸的概念與特性：遞歸本質類似循環，是通過函數體進行的循環操作。借助電影《盜夢空間》類比，遞歸如同主角在不同夢境層穿梭，向下進入不同遞歸層，向上能回到原來一層，每一層環境和周圍元素相似，主角在不同層級夢境中會發生變化并攜帶變化。
2. 遞歸的實現——計算n!：計算n的階乘（n!=1×2×3×…×n）是遞歸的經典示例。定義Factorial(n)函數，當n <= 1時返回1，否則返回n * Factorial(n - 1) 。以factorial(6)為例，詳細展示了遞歸計算過程。
3. 遞歸代碼模板
   • Python代碼模版：recursion(level, param1, param2, ...)函數結構為：先設置遞歸終止條件（if level > MAX_LEVEL），接著處理當前層邏輯（process(level, data...)），然后向下遞歸（self.recursion(level + 1, p1, ...)），最后根據需要恢復當前層狀態。
   • Java代碼模版：public void recur(int level, int param)方法同樣包含遞歸終止條件（if (level > MAX_LEVEL)）、當前邏輯處理（process(level, param)）、向下遞歸（recur(level: level + 1, newParam)）和恢復當前狀態（restore current status）這些關鍵部分。
4. 遞歸的思維要點
   • 摒棄人肉遞歸：避免手動模擬遞歸過程，這是理解遞歸的最大誤區，應直接依據函數定義編寫代碼。
   • 分解問題：找到最近最簡方法，將問題拆解成可重復解決的子問題，利用重復子問題簡化求解。
   • 運用數學歸納法思維：類似點燃炮竹，保證基礎情況（第一個炮竹能點燃）成立，假設某一情況（前一個炮竹能點燃）成立時能推出下一個情況（下一個炮竹能點燃）成立，以此構建遞歸邏輯。

習題

題目描述

給定一個正整數 (n) ，計算 (n) 的階乘 (n!) ，其中 (n! = 1\times2\times3\times\cdots\times n) ，需用Python語言編寫函數實現該計算。

最優解（即圖中代碼所示方法）

def Factorial(n):if n <= 1:return 1return n * Factorial(n - 1)

解析

• 遞歸終止條件： if n <= 1: return 1 這部分是遞歸的關鍵終止條件。因為 (0!) 和 (1!) 的值都為 (1) ，當函數參數 (n) 為 (0) 或者 (1) 時，直接返回 (1) ，不再繼續遞歸調用，避免無限循環。
• 遞歸調用： return n * Factorial(n - 1) 體現了階乘計算的核心邏輯。根據階乘的定義，(n!) 等于 (n) 乘以 ((n - 1)!) ，所以函數在 (n > 1) 時，通過不斷調用自身并將參數減 (1) ，逐步計算出最終結果。比如計算 (5!) ，函數會依次計算 (5\times4!) ， (4!) 又會計算為 (4\times3!) ，以此類推，直到遇到終止條件 (1!) 返回 (1) ，再逐步回代計算出最終結果。 這種遞歸實現簡潔且準確地表達了階乘的計算邏輯。

題目復述

爬樓梯（Climbing Stairs） ：假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？（來源：力扣 https://leetcode-cn.com/problems/climbing-stairs/ ）

最優解（遞歸實現思路，實際中更優解一般是迭代等方式 ）

def climbStairs(n):if n == 1:return 1if n == 2:return 2return climbStairs(n - 1) + climbStairs(n - 2)

分析

• 遞歸終止條件：當 n == 1 時，只有一種爬法，即一次爬一階，所以返回 1 ；當 n == 2 時 ，可以一次爬兩階，或者分兩次每次爬一階，共兩種爬法，返回 2 。這兩個條件是遞歸結束的標志，避免無限遞歸。
• 遞歸調用邏輯：對于 n > 2 的情況，到達第 n 階樓梯的方法數，等于到達第 n - 1 階樓梯的方法數加上到達第 n - 2 階樓梯的方法數。因為到達第 n 階樓梯，要么是從第 n - 1 階再爬一階上來的，要么是從第 n - 2 階一次爬兩階上來的。所以通過 return climbStairs(n - 1) + climbStairs(n - 2) 進行遞歸調用，不斷將問題規模縮小，直到滿足終止條件。

不過需要注意，純遞歸實現會存在大量重復計算，時間復雜度較高（指數級） 。實際應用中，更推薦使用迭代法（如動態規劃的迭代實現） 、矩陣快速冪等優化方法來降低時間復雜度。

題目描述

爬樓梯問題拓展

假設你正在爬樓梯，需要 n 階才能到達樓頂，每次你可以爬 1 個、2 個或 3 個臺階 ，求爬到樓頂有多少種不同的方法。

遞歸實現代碼

代碼展示

def climbStairs(n):if n == 1:return 1elif n == 2:return 2elif n == 3:return 4return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3)

代碼解析

遞歸終止條件

• 當 n == 1 時 ，只有一種爬法，即一次爬一階，所以返回 1 。
• 當 n == 2 時，有兩種爬法：一次爬兩階 ，或者分兩次每次爬一階，返回 2 。
• 當 n == 3 時，有四種爬法：（1, 1, 1） 、（1, 2）、（2, 1）、（3） ，返回 4 。這些條件是遞歸結束的標志，避免無限遞歸。

遞歸調用邏輯

對于 n > 3 的情況，到達第 n 階樓梯的方法數，等于到達第 n - 1 階樓梯的方法數、到達第 n - 2 階樓梯的方法數與到達第 n - 3 階樓梯的方法數之和 。因為到達第 n 階樓梯，要么是從第 n - 1 階再爬一階上來的，要么是從第 n - 2 階爬兩階上來的，要么是從第 n - 3 階爬三階上來的 。所以通過 return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3) 進行遞歸調用，不斷將問題規模縮小，直到滿足終止條件。

復雜度分析

時間復雜度

由于存在大量重復計算，時間復雜度為指數級，約為 (O(3^n)) ，隨著 n 的增大，計算量會急劇增加。

空間復雜度

主要取決于遞歸調用棧的深度，在最壞情況下為 (O(n)) 。

優化思路

動態規劃優化

這種純遞歸實現效率較低，存在大量重復計算。可采用動態規劃（如使用數組記錄中間結果避免重復計算） 、矩陣快速冪等方法優化，將時間復雜度降低。 例如動態規劃的迭代實現：

def climbStairs(n):if n == 1:return 1elif n == 2:return 2elif n == 3:return 4dp = [0] * ndp[0], dp[1], dp[2] = 1, 2, 4for i in range(3, n):dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]return dp[-1]

此方法用數組 dp 記錄爬到第 i 階的方法數，通過迭代計算，避免了重復計算，時間復雜度降為 (O(n)) ，空間復雜度也為 (O(n)) ，還可進一步優化空間復雜度。

題目描述

給定一個二叉樹的根節點 root，判斷該二叉樹是否為有效的二叉搜索樹。在二叉搜索樹中，對于任意節點，其左子樹中所有節點的值均小于該節點的值，右子樹中所有節點的值均大于該節點的值，并且左右子樹也都必須是二叉搜索樹。

最優解（Python 代碼）

# 定義二叉樹節點類
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def __init__(self):self.prev = float('-inf')  # 記錄中序遍歷的前一個節點值，初始化為負無窮def isValidBST(self, root):if not root:return True# 遞歸檢查左子樹if not self.isValidBST(root.left):return False# 檢查當前節點與前一個節點值的關系if root.val <= self.prev:return Falseself.prev = root.val# 遞歸檢查右子樹return self.isValidBST(root.right)

解析

1. 數據結構定義：首先定義了 TreeNode 類來表示二叉樹的節點，每個節點包含一個值 val ，以及指向左子節點 left 和右子節點 right 的指針。這是構建二叉樹和進行后續操作的基礎。
2. 類初始化：在 Solution 類的 __init__ 方法中，初始化了一個變量 prev ，并將其值設為負無窮 float('-inf') 。這個變量用于記錄在中序遍歷過程中前一個節點的值，以便在遍歷過程中比較當前節點值與前一個節點值的大小關系，從而判斷是否符合二叉搜索樹的規則。
3. 遞歸函數主體：
   • 遞歸終止條件：當 root 為空節點時，即 not root 條件成立，直接返回 True 。因為空樹被定義為有效的二叉搜索樹，不存在違反規則的情況。
   • 中序遍歷遞歸檢查左子樹：通過 self.isValidBST(root.left) 遞歸調用自身來檢查左子樹是否為有效的二叉搜索樹。如果左子樹不是有效的二叉搜索樹，直接返回 False ，無需繼續檢查當前節點和右子樹。這是因為只要二叉樹的任何一部分不符合規則，整個二叉樹就不是有效的二叉搜索樹。
   • 檢查當前節點：在左子樹檢查通過后，比較當前節點的值 root.val 和記錄的前一個節點的值 self.prev 。如果 root.val <= self.prev ，說明違反了二叉搜索樹中序遍歷結果應是升序序列的規則（即當前節點值應大于前一個節點值），返回 False 。如果當前節點值符合規則，則更新 self.prev 為當前節點的值 root.val ，為后續檢查右子樹做準備。
   • 中序遍歷遞歸檢查右子樹：通過 self.isValidBST(root.right) 遞歸調用自身來檢查右子樹是否為有效的二叉搜索樹。如果右子樹檢查通過，說明整個二叉樹是有效的二叉搜索樹，返回 True ；如果右子樹檢查不通過，則返回 False 。

算法復雜度

• 時間復雜度：該算法需要對二叉樹的每個節點進行一次訪問，所以時間復雜度為 (O(n)) ，其中 (n) 是二叉樹的節點數。
• 空間復雜度：在遞歸過程中，遞歸調用棧的深度最大為二叉樹的高度 (h) 。在最壞情況下（二叉樹為單鏈表形式），高度 (h = n) ，此時空間復雜度為 (O(n)) ；在最好情況下（二叉樹為完全平衡樹），高度 (h = \log n) ，空間復雜度為 (O(\log n)) 。

題目描述（翻轉二叉樹 - Invert Binary Tree ）

給定一棵二叉樹的根節點 root ，需要將這棵二叉樹進行翻轉，也就是交換每個節點的左右子樹。例如，對于二叉樹 root = [4,2,7,1,3,6,9] ，翻轉后應變為 [4,7,2,9,6,3,1] 。（題目來源：https://leetcode-cn.com/problems/invert-binary-tree/description/ ）

最優解（遞歸解法，Python 代碼）

# 定義二叉樹節點類
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef invertTree(root):if not root:return None# 交換左右子樹root.left, root.right = root.right, root.left# 遞歸翻轉左子樹invertTree(root.left)# 遞歸翻轉右子樹invertTree(root.right)return root

解析

1. 遞歸終止條件：當 root 為空節點時，即 not root ，直接返回 None 。因為空樹不需要進行翻轉操作。
2. 交換左右子樹：對于非空節點，使用 root.left, root.right = root.right, root.left 這行代碼交換當前節點的左右子樹。這是翻轉二叉樹的核心操作，直接改變了當前節點的子樹結構。
3. 遞歸調用：
   • 交換完當前節點的左右子樹后，通過 invertTree(root.left) 遞歸調用函數自身，對當前節點的左子樹進行翻轉。這是因為左子樹在交換后也需要進一步翻轉其內部的子樹結構。
   • 同理，通過 invertTree(root.right) 遞歸調用函數自身，對當前節點的右子樹進行翻轉。
4. 返回結果：最后返回翻轉后的根節點 root ，使得整個翻轉操作完成后能得到翻轉后的二叉樹的根節點，方便后續對整棵樹進行操作或訪問。

算法復雜度

• 時間復雜度：由于需要對二叉樹的每個節點進行一次訪問并交換其左右子樹，所以時間復雜度為 (O(n)) ，其中 (n) 是二叉樹的節點數。
• 空間復雜度：在遞歸過程中，遞歸調用棧的深度最大為二叉樹的高度 (h) 。在最壞情況下（二叉樹為單鏈表形式），高度 (h = n) ，此時空間復雜度為 (O(n)) ；在最好情況下（二叉樹為完全平衡樹），高度 (h = \log n) ，空間復雜度為 (O(\log n)) 。

題目描述

給定二叉樹的根節點 root，求該二叉樹的最大深度。二叉樹的最大深度是指從根節點到最遠葉子節點的最長路徑上的節點數 。例如，對于二叉樹 [3,9,20,null,null,15,7] ，其最大深度為 3，因為從根節點 3 到葉子節點 15 或 7 的路徑長度最長，為 3 。（題目來源：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree ）

最優解（遞歸解法，Python 代碼）

# 定義二叉樹節點類
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef maxDepth(root):if not root:return 0left_depth = maxDepth(root.left)right_depth = maxDepth(root.right)return max(left_depth, right_depth) + 1

解析

1. 遞歸終止條件：當 root 為空節點時，即 not root ，返回 0 。因為空樹沒有節點，其深度為 0 。
2. 遞歸計算子樹深度：
   • 通過 left_depth = maxDepth(root.left) 遞歸調用 maxDepth 函數，計算左子樹的最大深度，并將結果存儲在 left_depth 變量中。這是因為要得到整棵樹的最大深度，需要先知道左子樹的最大深度情況。
   • 同理，通過 right_depth = maxDepth(root.right) 遞歸調用 maxDepth 函數，計算右子樹的最大深度，并將結果存儲在 right_depth 變量中。
3. 計算整棵樹的最大深度：整棵樹的最大深度等于左子樹和右子樹中較大的深度值再加 1（加 1 是因為要算上根節點本身） ，通過 return max(left_depth, right_depth) + 1 實現這一計算并返回結果。

算法復雜度

• 時間復雜度：由于需要對二叉樹的每個節點進行一次訪問，所以時間復雜度為 (O(n)) ，其中 (n) 是二叉樹的節點數。
• 空間復雜度：在遞歸過程中，遞歸調用棧的深度最大為二叉樹的高度 (h) 。在最壞情況下（二叉樹為單鏈表形式），高度 (h = n) ，此時空間復雜度為 (O(n)) ；在最好情況下（二叉樹為完全平衡樹），高度 (h = \log n) ，空間復雜度為 (O(\log n)) 。

題目描述

給定一個二叉樹的根節點 root，求該二叉樹的最小深度。二叉樹的最小深度是指從根節點到最近葉子節點的最短路徑上的節點數。這里的葉子節點是指沒有子節點的節點。例如，對于二叉樹 [3,9,20,null,null,15,7] ，其最小深度為 2，因為從根節點 3 到葉子節點 9 的路徑長度最短，為 2 。（題目來源：https://leetcode-cn.com/problems/minimum - depth - of - binary - tree ）

最優解（Python 遞歸代碼實現）

# 定義二叉樹節點類
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef minDepth(root):if not root:return 0# 如果左子樹為空，最小深度取決于右子樹if not root.left:return minDepth(root.right) + 1# 如果右子樹為空，最小深度取決于左子樹if not root.right:return minDepth(root.left) + 1left_depth = minDepth(root.left)right_depth = minDepth(root.right)return min(left_depth, right_depth) + 1

解析

1. 遞歸終止條件：當 root 為空節點時，即 not root ，返回 0 。因為空樹沒有節點，其深度為 0 。
2. 特殊情況處理：
   • 當左子樹為空時，此時二叉樹的最小深度取決于右子樹，通過 if not root.left: return minDepth(root.right) + 1 來計算，這里加 1 是因為要算上根節點本身。
   • 當右子樹為空時，此時二叉樹的最小深度取決于左子樹，通過 if not root.right: return minDepth(root.left) + 1 來計算，同樣加 1 是算上根節點。
3. 正常情況遞歸計算：當左右子樹都不為空時，分別通過 left_depth = minDepth(root.left) 和 right_depth = minDepth(root.right) 遞歸計算左子樹和右子樹的最小深度，然后取兩者中的較小值再加 1（加上根節點） ，即 return min(left_depth, right_depth) + 1 ，得到整棵樹的最小深度。

算法復雜度

• 時間復雜度：算法需要遍歷二叉樹的每個節點，所以時間復雜度為 (O(n)) ，其中 (n) 是二叉樹的節點數。
• 空間復雜度：在遞歸過程中，遞歸調用棧的深度最大為二叉樹的高度 (h) 。在最壞情況下（二叉樹為單鏈表形式），高度 (h = n) ，此時空間復雜度為 (O(n)) ；在最好情況下（二叉樹為完全平衡樹），高度 (h = \log n) ，空間復雜度為 (O(\log n)) 。

題目描述

1. 序列化：給定一棵二叉樹的根節點 root，將其按照某種規則轉換為一個字符串，這個過程就是序列化。序列化的目的是將二叉樹的數據結構以一種可存儲或傳輸的形式表示出來。
2. 反序列化：給定一個通過序列化得到的字符串數據，將其重新構建成一棵二叉樹，這就是反序列化。要求反序列化得到的二叉樹與原始二叉樹在結構和節點值上完全一致。 （題目來源：https://leetcode-cn.com/problems/serialize - and - deserialize - binary - tree/ ）

最優解（Python 代碼實現）

# 定義二叉樹節點類
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Codec:def serialize(self, root):"""對二叉樹進行序列化"""def dfs(node):if not node:res.append('null')returnres.append(str(node.val))dfs(node.left)dfs(node.right)res = []dfs(root)return ','.join(res)def deserialize(self, data):"""對序列化后的字符串進行反序列化"""def helper():val = next(vals)if val == 'null':return Nonenode = TreeNode(int(val))node.left = helper()node.right = helper()return nodevals = iter(data.split(','))return helper()
# 示例用法
# codec = Codec()
# root = TreeNode(1)
# root.left = TreeNode(2)
# root.right = TreeNode(3)
# root.right.left = TreeNode(4)
# root.right.right = TreeNode(5)
# serialized = codec.serialize(root)
# deserialized_root = codec.deserialize(serialized)

解析

1. 定義二叉樹節點類：首先定義 TreeNode 類，用于表示二叉樹的節點，每個節點包含節點值 val ，以及指向左子節點 left 和右子節點 right 的指針。
2. 序列化方法 serialize
   • 內部定義了深度優先搜索（DFS）輔助函數 dfs 。在 dfs 函數中，當遇到空節點時，向結果列表 res 中添加 'null' ，表示空節點。當遇到非空節點時，將節點值轉換為字符串添加到 res 中，然后遞歸調用 dfs 分別處理左子樹和右子樹。
   • 最后通過 ','.join(res) 將結果列表中的元素以逗號連接成字符串，得到序列化后的結果。
3. 反序列化方法 deserialize
   • 內部定義了輔助函數 helper 。helper 函數通過 next(vals) 從迭代器 vals 中獲取下一個值。如果獲取到的值是 'null' ，表示當前節點為空，返回 None 。
   • 如果獲取到的值不是 'null' ，則創建一個新的 TreeNode 節點，其值為獲取到的值轉換后的整數。然后遞歸調用 helper 分別構建左子樹和右子樹，最后返回構建好的節點。
   • 通過 vals = iter(data.split(',')) 將輸入的序列化字符串按逗號分割后轉換為迭代器，方便 helper 函數依次獲取節點值或 'null' 標識，最終返回反序列化構建好的二叉樹的根節點。

算法復雜度

• 序列化時間復雜度：在序列化過程中，對二叉樹的每個節點進行一次訪問，時間復雜度為 (O(n)) ，其中 (n) 是二叉樹的節點數。
• 反序列化時間復雜度：反序列化時，同樣要處理序列化字符串中的每個元素（對應二叉樹的節點或空節點標識），時間復雜度也是 (O(n)) 。
• 空間復雜度：無論是序列化還是反序列化，在遞歸過程中，遞歸調用棧的深度最大為二叉樹的高度 (h) 。在最壞情況下（二叉樹為單鏈表形式），高度 (h = n) ，此時空間復雜度為 (O(n)) ；在最好情況下（二叉樹為完全平衡樹），高度 (h = \log n) ，空間復雜度為 (O(\log n)) 。此外，序列化結果存儲也需要 (O(n)) 的空間。