初识分治思想(跑路人笔记)

2022-06-22 132

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 初识分治思想(跑路人笔记)

前言

今天的分治思想是我在学树的时候的前序中序后序遍历以及后面一些题目都用到的一种思想,后面好像还有一种排序也需要用到这个分治的思想,所以舒文想努努力吧这个思想搞明白清楚一些也给大家提供一个参考.本次主要以大量题目为主,所以大家不用担心会出现大量理论性东西.

正文

分治的基本思想

分治分治,分而治之,当我们遇到一个问题无法或难以直接通过思考得到答案时我们就可以通过将这个大问题分成若干个类似的子问题,然后通过多次解决子问题然后合并最后得到我们想要的答案.

分治思想

分治的基本思想

将这个大问题分成若干个类似的子问题,然后通过多次解决子问题然后合并最后得到我们想要的答案.

需注意的是我们的子问题之间是独立的不能互相影响不然将无法使用分治思想

例题讲解

例题一<相同的树>

相同的树

这道题我们就可以用分治的思想来讲解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p == NULL && q == NULL)//两个都为空的子问题时也为真
        return true;
    if(p == NULL)//和下面那个if条件句一样经历了上个却没被返回时p,q不可能同时为空了
        return false;
    if(q == NULL)
        return false;
    if(p->val != q->val)//不等时直接为假,这个条件成立后我们就需要所有都为
    {
        return false;
    }
    return isSameTree(p->right,q->right) && isSameTree(p->left,q->left);//使用&&会使一个假就所有都为假,也可使用*来代替
}

我们就通过上面的[1,2,3] [1,2,3]的例子来讲解

我们将每个节点都作为一个子问题来看待.所以我们就要分析子问题一共能带来的类型是多少.

四种类型

p,q同为NULL时,同为空时的pq也是相等的返回true

p为空q不为空返回false

q为空p不为空返回false

都不为空但是p和q的val不相同也要返回false

子问题的类型一共只有这么多种最后再return的时候我们要将所有的子问题进行综合.

因为right和left两遍任意一个为假的时候我们的树都不相同所有我们就使用&&来将假的都为假.

例题二<对称二叉树>

101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)

镜面对称,所以我们的根节点我们可以直接忽略,只需看左右节点是否可以镜面对称即可,所以我们要得到左右节点的地址并放在同一个函数内进行递归比较.所以我们可以再开辟一个函数来达到这个目的.

如下

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSymmetric(struct TreeNode* p,struct TreeNode* q)//我们自己的函数
{
    if(p==NULL&&q==NULL)//同为NULL可
        return true;
    else if(p==NULL||q==NULL)//一个为空一个不为空不可
        return false;
    if(p->val!=q->val)//我们将子问题分为单个节点问题进行递归调整
        return false;
    return _isSymmetric(p->left,q->right)&&_isSymmetric(p->right,q->left);//通过递归调整
}
bool isSymmetric(struct TreeNode* root)
{
    return _isSymmetric(root->right,root->left);//根节点无意义直接省略即可.
}

我们在用分治思想的时候就要考虑到每个子问题的带来的问题,并考虑好我们要得到的结果即可,在结合部分我们也要从根据条件进行调整

例题三<二叉树的前序遍历>

144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

我们要返回前序遍历得到数值的数组,数组是要通过malloc来得到空间的.

我们先看看代码吧:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 int Bsize(struct TreeNode* root)
 {
    if(root==NULL)
        return 0;
    return Bsize(root->left)+Bsize(root->right)+1;//依旧使用了分治的思想
 }
 void _preorderTraversal(struct TreeNode* root,int *arr,int* pi)
 {
    if(root == NULL)//为空的时候直接结束进程
        return;
    //后面的root就不可能为空了
    arr[*pi] = root->val;//先得到根的数值
    (*pi)++;
    _preorderTraversal(root->left,arr,pi);//前序就先left
    _preorderTraversal(root->right,arr,pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = Bsize(root);
    int *arr = (int*)malloc(sizeof(int)*(*returnSize));
    int i = 0;
    _preorderTraversal(root,arr,&i);//传i是为了在递归的时候记录下标
    return arr;
}