采用递归的方法，在实际应用中可以很大程度的提高代码的可读性，令代码易于维护，但是在计算时间复杂度和空间复杂度时，显然对于递归来说就不是那么的容易。
采用递归的思路的核心在于分治法，即将问题拆解。
21 合并两个有序链表
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1 == nullptr)return l2;else if(l2 == nullptr)return l1;else if(l1->val < l2->val){l1->next = mergeTwoLists(l1->next, l2);return l1;}else{l2->next = mergeTwoLists(l1, l2->next);return l2;}}};
这道题还可以采用迭代的方法
class Solution {public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* preHead = new ListNode(-1);ListNode* prev = preHead;while (l1 != nullptr && l2 != nullptr) {if (l1->val < l2->val) {prev->next = l1;l1 = l1->next;} else {prev->next = l2;l2 = l2->next;}prev = prev->next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev->next = l1 == nullptr ? l2 : l1;return preHead->next;}};作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
46 全排列
46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这里就是将复杂的问题进行分拆，分成两部分，只有一个数字和另外一个待需排列的数组，通过递归的方式进行实现
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>>ret;
if(nums.size() == 0)
return ret;
if(nums.size() == 1)
return vector<vector<int>>{{nums[0]}};
for(int i = 0; i < nums.size(); i++)
{
vector<int>part(nums.begin(), nums.begin() + i);
part.insert(part.end(), nums.begin() + i + 1, nums.end());
vector<vector<int>>tmp_ret = permute(part);
for(auto &vec : tmp_ret)
{
vec.insert(vec.begin(), nums[i]);
ret.push_back(vec);
}
}
return ret;
}
};
236 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
通过次数163,996提交次数246,602
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
同样的道理，将细节交给递归来做，唯一需要找准的就是递归的终止条件
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool findNode(TreeNode* root, TreeNode *node)
{
if(root == node)
return true;
if(root == NULL)
return false;
return findNode(root->left, node) || findNode(root->right, node);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == p || root == q)
return root;
if(root == NULL)
return NULL;
if(findNode(root->left, p) && findNode(root->left, q))
return lowestCommonAncestor(root->left, p, q);
else if(findNode(root->right, p) && findNode(root->right, q))
return lowestCommonAncestor(root->right, p, q);
else
return root;
}
};
226 翻转二叉树
226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4/ \
2 7
/ \ / \
1 3 6 9
输出：
4/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
在做这道题的时候，注意需要一个暂存点保存左子树后或是右子树的翻转结果，否则，已经被翻转后的结果是不能被继续使用的，比如已经翻转了root->left, 接下来就不能将原始的root->left传入到函数中进行翻转了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr)
return root;
TreeNode *tmp = invertTree(root->right);
root->right = invertTree(root->left);
root->left = tmp;
return root;
}
};
124 二叉树中的最大路径和
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题在利用递归的时候，需要想清楚递归返回的值所代表的含义，在这里递归的返回值指的是当前节点所可以贡献的最大值，而非当前节点的最大路径和。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int ans = INT_MIN;
int pathSum(TreeNode* root)
{
if(root == nullptr)
return 0;
int left = max(0, pathSum(root->left));
int right = max(0, pathSum(root->right));
ans = max(ans, left + root->val + right);
return max(left, right) + root->val;
}
int maxPathSum(TreeNode* root) {
ans = INT_MIN;
pathSum(root);
return ans;
}
};
两两交换链表中的节点
24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode *next = head->next;
ListNode* combine = swapPairs(next->next);
next->next = head;
head->next = combine;
return next;
}
};
若有收获，就点个赞吧
0 人点赞
