本章节是总结学习二叉树,排序算法等等递归问题所总结的,对递归,搜索,回溯的算法进行总结
函数自己调用自己的情况
本质:解决一个问题,出现相同的子问题
例子展示:
//后序遍历
void dfs(TreeNode* root)
{
//细节 - 出口
if (root == nullptr)
return;
dfs(root->left);//只需相信dfs这个黑盒能帮我完成遍历左子树任务,不需要关注细节展开图
dfs(root->right);//只需相信dfs这个黑盒能帮我完成遍历右子树任务,不需要关注细节展开图
cout << root->val;
}
class Solution {
public:
void _merger(vector<int>& nums, int left, int right, int* tmp)
{
//细节 - 出口
if (left >= right)
return;
int mid = (left + right) / 2;
_merger(nums, left, mid, tmp);//只需相信给你中间值和需要参数_merge这个黑盒能帮我完成排序左区间,不需要关注细节展开图
_merger(nums, mid + 1, right, tmp);
//只需相信给你中间值和需要参数_merge这个黑盒能帮我完成排序右区间,不需要关注细节展开图
//merge操作..
// int begin1 = left, end1 = mid;
// int begin2 = mid + 1, end2 = right;
// int i = left;
// while (begin1 <= end1 && begin2 <= end2)
// {
// if (nums[begin1] <= nums[begin2])
// {
// tmp[i++] = nums[begin1++];
// }
// else
// {
// tmp[i++] = nums[begin2++];
// }
// }
// while (begin1 <= end1)
// {
// tmp[i++] = nums[begin1++];
// }
// while (begin2 <= end2)
// {
// tmp[i++] = nums[begin2++];
// }
// memcpy(nums.data() + left, tmp + left, (right - left + 1) * sizeof(int));
//}
//vector<int> sortArray(vector<int>& nums) {
// int* tmp = new int[nums.size()];
// _merger(nums, 0, nums.size() - 1, tmp);
// delete[] tmp;
// return nums;
//}
};
搜索:暴力枚举一遍所有的情况 搜索等同于暴搜:两种方法进行
将一个问题进行一 一罗列(全排列)出所有的可能组合,然后用树状图的方法来画出决策树
回溯算法的特点是先尝试并检查解决方案,如果当前解决方案不可行,就回到上一个决策点继续尝试其他的可能性。
后续文章继续继续总结