[TOC] ## 介绍 将大问题转化为小问题，通过递归依次解决各个小问题 ## 示例 #### [24\. 两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs/) 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 **你不能只是单纯的改变节点内部的值**，而是需要实际的进行节点交换。 ``` public: ListNode* swapPairs(ListNode* head) { // 思路：将链表翻转转化为一个子问题，然后通过递归方式依次解决 // 先翻转两个，然后将后面的节点继续这样翻转，然后将这些翻转后的节点连接起来 return helper(head); } ListNode* helper(ListNode* head) { if (head == NULL || head->next == NULL) return head; // 保存下一阶段的头指针 ListNode* nextHead = head->next->next; // 翻转当前两个节点 ListNode* next = head->next; next->next = head; head->next = helper(nextHead); return next; } }; ``` #### [95\. 不同的二叉搜索树 II](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/) 给定一个整数 *n*，生成所有由 1 ... *n* 为节点所组成的 **二叉搜索树** ``` class Solution { public: vector<TreeNode*> generateTrees(int n) { if (n == 0) return {}; return generate(1, n); } vector<TreeNode*> generate(int left, int right) { vector<TreeNode*> result; if (left > right) { result.push_back(NULL); return result; } for (int i = left; i <= right; i++) { vector<TreeNode*> lefts = generate(left, i - 1); vector<TreeNode*> rights = generate(i + 1, right); for (auto l : lefts) { for (auto r : rights) { TreeNode* node = new TreeNode(i, l, r); result.push_back(node); } } } return result; } }; ```