目录

分治算法

例一：相同的树

例二：单值二叉树

例三：二叉树的最大深度

作者新建立的社区：非科班转码社区-CSDN社区云💖💛💙

期待hxd的支持哈🎉 🎉 🎉

分治算法

思想

思想就是大问题分成相同问题的子问题。

分治就是递归。

分治法在每一层递归上都有三个步骤：

    step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

    step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

    step3 合并：将各个子问题的解合并为原问题的解。

下面我们用三个简单的例子来深入理解分治算法。每题代码里面都有注释哈。（配原题链接）

例一：相同的树

原文链接

 

/** * 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 || q==NULL)    return false;    //不相等 返回假    if(p->val!=q->val)    return false;    //左右子树递归    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);}

例二：单值二叉树

原文链接

 

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     struct TreeNode *left; *     struct TreeNode *right; * }; *///int flag=0;//int temp=0;bool _isUnivalTree(struct TreeNode* root, int val){    if(root==NULL)    return true;    if(root->val!=val)    return false;    return _isUnivalTree(root->left, val)     && _isUnivalTree(root->right, val);}bool isUnivalTree(struct TreeNode* root){/*解题思路：遍历二叉树，并且每一个节点值都和根节点的值进行比对，如果不等于根节点的值，则不是单值树。*/    if(root==NULL)    return true;    int val=root->val;    return _isUnivalTree(root,val);/    // if(root==NULL)    // return true;    // if(temp==0)    // {    // flag=root->val;    // temp=1;    // }    // else    // {    //     if(root->val!=flag)    //     return false;    // }    // flag=0;    // isUnivalTree(root->left);    // flag=0;    // isUnivalTree(root->right);    // return true;}

例三：二叉树的最大深度

原文链接

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     struct TreeNode *left; *     struct TreeNode *right; * }; */int maxDepth(struct TreeNode* root){    //左最大深度+1  右最大深度+1    //root==NULL return 0    if(root==NULL)    return 0;    int leftDepth=maxDepth(root->left);    int rightDepth=maxDepth(root->right); return leftDepth>rightDepth?leftDepth+1:rightDepth+1;}

最后的最后，创作不易，希望读者三连支持💖

赠人玫瑰，手有余香💖