• 什么是遞歸？
  函數自己調用自己的情況
• 為什么會用到遞歸？
  本質：在解決主問題的時候衍生出一個相同處理過程的子問題，子問題再繼續衍生子問題…
• 如何理解遞歸？
  • 第一層次的理解：遞歸展開的細節圖
  • 第二層次的理解：二叉樹題目練習
  • 第三層次的理解：宏觀看待遞歸過程
    • a. 不要再在意遞歸的細節展開圖
    • b. 把遞歸的函數當成一個黑盒
    • c. 相信這個黑盒一定能完成既定任務
• 如何寫好一個遞歸？
  • a. 先找到主問題和子問題的相同處理過程！！！-> 可以用于處理函數頭的設計
  • b. 只關心某一個子問題是如何解決的 -> 可以用于處理函數體的書寫
  • c. 注意一下遞歸函數的出口即可\

1. 漢諾塔問題

找到主問題和子問題的相同處理過程 -> 用于處理函數頭的設計:n個盤子，從A柱子，借助B柱子，移動到C柱子 -> void dfs(int n, vector<int>& A, vector<int>& B, vector<int>& C)

void dfs(int n, vector<int>& A, vector<int>& B, vector<int>& C)
{if(n == 1){C.push_back(A.back());A.pop_back();return;}dfs(n-1, A, C, B);C.push_back(A.back());A.pop_back();dfs(n-1, B, A, C);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
{dfs(A.size(), A, B, C);
}

2. 合并兩個有序鏈表

找到主問題和子問題的相同處理過程 -> 用于處理函數頭的設計:合并兩個有序鏈表 -> ListNode* dfs(list1, list2);

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{if(list1 == nullptr) return list2;else if(list2 == nullptr) return list1;if(list1->val <= list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}else{list2->next = mergeTwoLists(list1, list2->next);return list2;}
}

3. 反轉鏈表

找到主問題和子問題的相同處理過程 -> 用于處理函數頭的設計:反轉一個鏈表 -> ListNode* dfs(list1);

ListNode* reverseList(ListNode* head)
{if(head == nullptr || head->next == nullptr) return head;ListNode* newHead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newHead;
}

4. 兩兩交換鏈表中的節點

找到主問題和子問題的相同處理過程 -> 用于處理函數頭的設計:兩兩交換鏈表中的節點 -> ListNode* dfs(ListNode* list1)

ListNode* swapPairs(ListNode* head)
{if(head == nullptr || head->next == nullptr) return head;ListNode* newHead = head->next;head->next = newHead->next;newHead->next = head;head->next = swapPairs(head->next);return newHead;
}

5. Pow(x, n)

找到主問題和子問題的相同處理過程 -> 用于處理函數頭的設計:求 x 的 n 次冪 -> int dfs(int x, int n);

double dfs(double x, int n)
{if(n == 0) return 1;double tmp = dfs(x, n / 2);return n % 2 ? tmp * tmp * x : tmp * tmp;
}
double myPow(double x, int n)
{if(n > 0) return dfs(x, n);else return 1 / dfs(x, n);
}

6. 計算布爾二叉樹的值

找到主問題和子問題的相同處理過程 -> 用于處理函數頭的設計:返回一棵完整二叉樹的布爾值 -> bool dfs(TreeNode* root);

bool evaluateTree(TreeNode* root)
{if(root->val == 0) return false;else if(root->val == 1) return true;if(root->val == 2) return evaluateTree(root->left) || evaluateTree(root->right);else return evaluateTree(root->left) && evaluateTree(root->right);
}

7. 求根節點到葉節點數字之和

int dfs(TreeNode* root, int val)
{val = val * 10 + root->val;if(root->left == nullptr && root->right == nullptr) return val;int left = 0, right = 0;if(root->left) left = dfs(root->left, val);if(root->right) right = dfs(root->right, val);return left + right;
}
int sumNumbers(TreeNode* root)
{return dfs(root, 0);
}

8. 二叉樹剪枝

TreeNode* pruneTree(TreeNode* root)
{if(root == nullptr) return nullptr;root->left = pruneTree(root->left);root->right = pruneTree(root->right);if(root->left == nullptr && root->right == nullptr && root->val == 0)return nullptr;return root;
}

9. 驗證二叉搜索樹

二叉搜索樹的中序遍歷是有序的

long long prev = LLONG_MIN;
bool isValidBST(TreeNode* root)
{if(root == nullptr) return true;// 剪枝if(isValidBST(root->left) == false) return false;if (prev < (root->val)) prev = root->val;else return false; // 剪枝return isValidBST(root->right);
}

10. 二叉搜索樹中第K小的元素

int value = -1;
int count = 0;
void dfs(TreeNode* root)
{if(root == nullptr) return;dfs(root->left);if(count == 0) return;if(value < root->val){value = root->val;--count;}dfs(root->right);
}
int kthSmallest(TreeNode* root, int k)
{count = k;dfs(root);return value;
}

11. 二叉樹的所有路徑

vector<string> v;
void dfs(TreeNode* root, string s)
{if(root->left == nullptr && root->right == nullptr){s += to_string(root->val);v.push_back(s);return;}s += to_string(root->val);s += "->";if(root->left) dfs(root->left, s);if(root->right) dfs(root->right, s);
}
vector<string> binaryTreePaths(TreeNode* root)
{dfs(root, "");return v;
}