遞歸與二叉樹遍歷青銅挑戰

理解遞歸

遞歸算法是指一個方法在其執行過程中調用自身。它通常用于將一個問題分解為更小的子問題，通過重復調用相同的方法來解決這些子問題，直到達到基準情況（終止條件）。

遞歸算法通常包括兩個主要部分：

1. 基準情況（也叫遞歸終止條件）：當問題規模足夠小，遞歸可以停止，通常返回一個簡單的結果。
2. 遞歸部分：將問題分解成更小的子問題，并在遞歸過程中調用自身。

為了更清晰地說明遞歸，我給你一個經典的例子：階乘計算。階乘是一個整數和它以下所有整數的乘積。記作：n! = n * (n-1) * ... * 1，而遞歸的數學定義是：

• n! = n * (n-1)!
• 基本情況：1! = 1 或 0! = 1

下面是一個使用Java編寫的遞歸算法來計算階乘的示例代碼：

class Factorial {public static int factorial(int n){//基準情況if(n == 0 || n == 1){return 1;}//遞歸部分return n * factorial(n - 1);} public static void main(String[] args){int num = 5;int result = factorial(num);System.err.println(num + "! = " + result);}
}

我們之前進行鏈表反轉使用的是迭代法，回顧一下：

public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next; // 臨時保存下一個節點curr.next = prev;              // 反轉當前節點的指針prev = curr;                   // 前移 prev 和 curr 指針curr = nextTemp;}return prev;                       // 返回新的頭結點
}

• 時間復雜度：O(N)，需要遍歷整個鏈表一次。
• 空間復雜度：O(1)，僅使用了固定數量的額外空間。

鏈表反轉同樣可以通過遞歸法實現，

public ListNode reverseList(ListNode head) {// 基準情況if (head == null || head.next == null) {return head;}// 遞歸調用ListNode newHead = reverseList(head.next);// 反轉當前節點和下一個節點的指向head.next.next = head;  // 當前節點的下一個節點指向當前節點head.next = null;       // 當前節點的 next 指向 null// 返回新的頭節點return newHead;
}

通過遞歸方法反轉鏈表簡潔且易于理解，但需注意其空間復雜度較高（O(n)），因為每次遞歸都會增加調用棧的空間消耗。相比之下，迭代法的空間復雜度更低（O(1)），但在代碼可讀性上稍遜于遞歸法。

遞歸與二叉樹遍歷白銀挑戰

二叉樹遍歷的遞歸寫法

遞歸實現二叉樹的前序、中序、后序遍歷的思路是基于樹的深度優先搜索（DFS）。以下是遞歸實現這三種遍歷方式的代碼，并附有解釋：

1. 二叉樹節點定義

首先，定義一個二叉樹節點（TreeNode）類：

static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;this.left = null;this.right = null;}
}

2. 前序遍歷（Preorder Traversal）

前序遍歷的順序是：根節點 → 左子樹 → 右子樹

public void preorderTraversal(TreeNode root) {if (root == null) {return;  // 遞歸終止條件}System.out.print(root.val + " ");  // 訪問根節點preorderTraversal(root.left);      // 遞歸遍歷左子樹preorderTraversal(root.right);     // 遞歸遍歷右子樹
}

解釋：

• 首先訪問根節點，然后遞歸遍歷左子樹，再遞歸遍歷右子樹。

3. 中序遍歷（Inorder Traversal）

中序遍歷的順序是：左子樹 → 根節點 → 右子樹

public void inorderTraversal(TreeNode root) {if (root == null) {return;  // 遞歸終止條件}inorderTraversal(root.left);       // 遞歸遍歷左子樹System.out.print(root.val + " ");  // 訪問根節點inorderTraversal(root.right);      // 遞歸遍歷右子樹
}

解釋：

• 先遞歸遍歷左子樹，然后訪問根節點，最后遞歸遍歷右子樹。

4. 后序遍歷（Postorder Traversal）

后序遍歷的順序是：左子樹 → 右子樹 → 根節點

public void postorderTraversal(TreeNode root) {if (root == null) {return;  // 遞歸終止條件}postorderTraversal(root.left);     // 遞歸遍歷左子樹postorderTraversal(root.right);    // 遞歸遍歷右子樹System.out.print(root.val + " ");  // 訪問根節點
}

總結

遞歸實現的核心在于每次對樹的左右子樹進行遞歸操作，遞歸的終止條件是節點為空。當節點不為空時，根據遍歷順序訪問當前節點的值。

假設我們有以下的二叉樹：

        1/ \2   3/ \ 4   5

用以下代碼來測試遍歷：

public class BinaryTreeTraversal {public static void main(String[] args) {// 創建二叉樹TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);BinaryTreeTraversal tree = new BinaryTreeTraversal();System.out.println("Preorder Traversal:");tree.preorderTraversal(root);System.out.println("\nInorder Traversal:");tree.inorderTraversal(root);System.out.println("\nPostorder Traversal:");tree.postorderTraversal(root);}
}

輸出結果：

Preorder Traversal:
1 2 4 5 3 Inorder Traversal:
4 2 5 1 3 Postorder Traversal:
4 5 2 3 1 

遞歸與二叉樹遍歷黃金挑戰

二叉樹遍歷的迭代寫法

• 前序遍歷：通過棧控制順序，根節點先訪問，再左子樹，最后右子樹。
• 中序遍歷：使用棧模擬遞歸，把左子樹入棧后訪問根節點，再訪問右子樹。
• 后序遍歷：使用兩個棧，第一個棧負責遍歷節點，第二個棧記錄節點的訪問順序，最后輸出。

這三種迭代實現都利用棧來模擬遞歸過程，棧的先進后出特性在遍歷過程中起到了關鍵作用。

1. 前序遍歷的迭代實現

前序遍歷順序： 根節點 → 左子樹 → 右子樹

前序遍歷的迭代實現我們使用棧來模擬遞歸過程，下面是詳細步驟。

• 初始化棧： 我們首先將根節點入棧，因為我們從根節點開始遍歷。
• 循環遍歷：
  1. 每次從棧中彈出一個節點，訪問它的值。
  2. 訪問節點之后，需要按照前序遍歷的規則，先將右子樹入棧，再將左子樹入棧。這樣做的目的是保證左子樹會先被訪問到。
  3. 如果節點有右子樹或左子樹，就按順序將它們入棧，棧是先進后出的結構，所以下次彈出的節點會先訪問到左子樹。

public void preorderTraversal(TreeNode root) {if (root == null) {return;  // 如果樹為空，直接返回}Stack<TreeNode> stack = new Stack<>();  // 創建一個棧來存儲節點stack.push(root);  // 將根節點入棧while (!stack.isEmpty()) {  // 當棧不為空時，繼續循環TreeNode node = stack.pop();  // 彈出棧頂元素（當前節點）System.out.print(node.val + " ");  // 訪問當前節點// 先右子樹入棧，再左子樹入棧，保證左子樹先被訪問if (node.right != null) {stack.push(node.right);  // 如果右子樹不為空，先將右子樹入棧}if (node.left != null) {stack.push(node.left);  // 如果左子樹不為空，再將左子樹入棧}}
}

2. 中序遍歷的迭代實現

中序遍歷順序： 左子樹 → 根節點 → 右子樹

中序遍歷的迭代實現使用一個棧來模擬遞歸過程，具體過程如下。

• 步驟 1： 我們從根節點開始，逐層將左子樹的節點入棧。棧會保存當前節點，并且我們一直往左走，直到遇到最左的節點。
• 步驟 2： 如果當前節點為空（說明已經到達葉子節點的左子樹），就彈出棧頂元素并訪問它，訪問完后轉到右子樹。
• 步驟 3： 訪問完當前節點后，將指針轉向其右子樹，繼續執行類似的過程。
• 棧的作用： 棧幫助我們記錄從根到最左葉節點的路徑，并確保訪問完左子樹后再訪問根節點，再訪問右子樹。

public void inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode current = root;  // 從根節點開始while (current != null || !stack.isEmpty()) {  // 當棧不為空，或者當前節點不為空時，繼續遍歷// 1. 將當前節點及其所有左子樹入棧while (current != null) {stack.push(current);  // 將當前節點入棧current = current.left;  // 然后將當前節點移到左子節點}// 2. 彈出棧頂元素并訪問current = stack.pop();  // 彈出棧頂元素System.out.print(current.val + " ");  // 訪問當前節點// 3. 轉到右子樹current = current.right;  // 處理右子樹}
}

3. 后序遍歷的迭代實現

后序遍歷順序： 左子樹 → 右子樹 → 根節點

后序遍歷的迭代實現稍微復雜一些，因為我們需要逆序訪問根、右子樹、左子樹。為了實現這一點，我們可以使用兩個棧來模擬遞歸過程。

• 棧 1（stack1）： 用來存儲節點，遍歷順序是根 → 右子樹 → 左子樹。我們先將根節點入棧，然后每次彈出棧頂節點并將其左右子樹入棧（右子樹先入棧）。
• 棧 2（stack2）： 用來存儲節點的訪問順序。因為棧是后進先出的，所以訪問的順序是根 → 右子樹 → 左子樹。最終，我們需要從 stack2 中彈出節點，才能得到正確的后序遍歷順序（左子樹 → 右子樹 → 根節點）。
• 兩個棧的作用： 第一個棧負責遍歷，第二個棧負責記錄節點的訪問順序，最終通過第二個棧實現后序遍歷的輸出。

public void postorderTraversal(TreeNode root) {if (root == null) {return;  // 如果樹為空，直接返回}Stack<TreeNode> stack1 = new Stack<>();  // 用于存儲遍歷的節點Stack<TreeNode> stack2 = new Stack<>();  // 用于存儲節點的訪問順序stack1.push(root);  // 將根節點入棧while (!stack1.isEmpty()) {  // 當 stack1 不為空時繼續循環TreeNode node = stack1.pop();  // 彈出棧頂元素stack2.push(node);  // 將該節點放入 stack2// 先左子樹入棧，再右子樹入棧if (node.left != null) {stack1.push(node.left);}if (node.right != null) {stack1.push(node.right);}}// stack2 中存放的是根、右子樹、左子樹的順序，我們需要反轉輸出while (!stack2.isEmpty()) {System.out.print(stack2.pop().val + " ");  // 彈出 stack2 中的元素并訪問}
}