在二叉樹的題目中，我們難免會(huì)用到遞歸方法，遞歸思想很簡(jiǎn)單，但運(yùn)用起來(lái)卻因?yàn)槌橄蠖y以理解。

理解遞歸的關(guān)鍵在于認(rèn)識(shí)到它是一種解決問(wèn)題的方法，允許函數(shù)直接或間接地調(diào)用自身。以下是對(duì)遞歸的概述以及如何理解它的幾個(gè)要點(diǎn)：

1. 基本概念

遞歸是用一個(gè)函數(shù)調(diào)用其自身來(lái)解決問(wèn)題。每次遞歸調(diào)用都會(huì)處理問(wèn)題的一部分，直到達(dá)到一個(gè)基本情況（即停止條件）。

2. 結(jié)構(gòu)

通常，遞歸包含兩部分：

• 基本情況（Base Case）：這是停止遞歸的條件。沒(méi)有這個(gè)條件，遞歸將無(wú)限進(jìn)行，導(dǎo)致棧溢出。
• 遞歸情況（Recursive Case）：這是函數(shù)調(diào)用自身以解決更小的子問(wèn)題。

3. 示例：階乘

一個(gè)經(jīng)典的遞歸示例是計(jì)算階乘。定義階乘的遞歸形式如下：

• ( n! = n \times (n-1)! )（遞歸情況）
• ( 0! = 1 )（基本情況）

其實(shí)現(xiàn)如下：

def factorial(n: int) -> int:if n == 0:  # 基本情況return 1else:  # 遞歸情況return n * factorial(n - 1)

在調(diào)用 factorial(5) 時(shí)，實(shí)際的調(diào)用過(guò)程是這樣的：

• factorial(5) 計(jì)算 5 * factorial(4)
• factorial(4) 計(jì)算 4 * factorial(3)
• factorial(3) 計(jì)算 3 * factorial(2)
• factorial(2) 計(jì)算 2 * factorial(1)
• factorial(1) 計(jì)算 1 * factorial(0)
• factorial(0) 返回 1

4. 可視化遞歸

為了幫助理解遞歸，可以使用樹結(jié)構(gòu)來(lái)可視化。例如，當(dāng)計(jì)算 factorial(5) 時(shí)，可以畫出一棵樹，顯示每個(gè)函數(shù)調(diào)用如何分支到下一個(gè)調(diào)用。最終，每個(gè)分支都返回結(jié)果，匯總至最頂層的函數(shù)。

5. 遞歸的問(wèn)題解決步驟

獲取遞歸解法的一般步驟：

1. 定義問(wèn)題：了解要解決的具體問(wèn)題。
2. 找出基本情況：明確何時(shí)停止遞歸。
3. 確定遞歸關(guān)系：如何將大問(wèn)題拆分為更小的子問(wèn)題。
4. 通過(guò)示例理解執(zhí)行過(guò)程：逐步追蹤函數(shù)調(diào)用，以深入理解每一步的作用。

6. 遞歸 vs 迭代

• 遞歸方法可以有更簡(jiǎn)潔和更具可讀性的實(shí)現(xiàn)，但有時(shí)更容易導(dǎo)致性能問(wèn)題（例如過(guò)多的函數(shù)調(diào)用可能導(dǎo)致棧溢出）。
• 循環(huán)（或迭代）通常會(huì)更高效，尤其是在不需要存儲(chǔ)調(diào)用棧的情況下。

7. 實(shí)踐

解決各種問(wèn)題（如遍歷樹、斐波那契數(shù)列、背包問(wèn)題等）可以加強(qiáng)對(duì)遞歸的理解。實(shí)踐是掌握遞歸最有效的方式。

我們來(lái)看看力扣144題目：二叉樹的前序遍歷


代碼不好理解的話，可以在自己的電腦上運(yùn)行下面的代碼。

from typing import Optional, List  # 定義二叉樹節(jié)點(diǎn)類  
class TreeNode:  def __init__(self, val=0, left=None, right=None):  self.val = val  self.left = left  self.right = right  # 定義Solution類并實(shí)現(xiàn)前序遍歷方法  
class Solution:  def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:  # 打印當(dāng)前節(jié)點(diǎn)的值  if not root:  print("當(dāng)前節(jié)點(diǎn): None")  return []  print(f"當(dāng)前節(jié)點(diǎn): {root.val}")  result = []  result.append(root.val)  # 添加根節(jié)點(diǎn)的值  print(f"當(dāng)前結(jié)果: {result}")  # 打印結(jié)果  # 遞歸遍歷左子樹  left_result = self.preorderTraversal(root.left)  result.extend(left_result)  # 遞歸遍歷右子樹  right_result = self.preorderTraversal(root.right)  result.extend(right_result)  print(f"返回結(jié)果: {result}")  # 打印返回的結(jié)果  return result  # 示例：創(chuàng)建一棵二叉樹并運(yùn)行前序遍歷  
if __name__ == "__main__":  # 創(chuàng)建二叉樹  #      1  #     / \#    2   3  #   / \#  4   5  root = TreeNode(1)  root.left = TreeNode(2)  root.right = TreeNode(3)  root.left.left = TreeNode(4)  root.left.right = TreeNode(5)  # 創(chuàng)建解決方案實(shí)例并調(diào)用前序遍歷  solution = Solution()  result = solution.preorderTraversal(root)  # 輸出最終結(jié)果  print(f"最終前序遍歷結(jié)果: {result}")  # 輸出應(yīng)為 [1, 2, 4, 5, 3]

下面是圖解遞歸算法：

前序遍歷的順序是：中左右。我們?nèi)绾卫眠f歸方法解決此道題目呢？我們可以假設(shè)一個(gè)簡(jiǎn)單的情況（root）不為空。

前序遍歷，我們先把中值root.val添加到result中。接下來(lái)我們要處理左節(jié)點(diǎn)了，左節(jié)點(diǎn)也是要中左右，這個(gè)時(shí)候我們可以借助遞歸來(lái)處理這種重復(fù)的動(dòng)作。

我們以下面的二叉樹為例：

遞歸算法里其實(shí)就是在做三件事：