分治算法
思想
思想就是大问题分成相同问题的子问题。
分治就是递归。
分治法在每一层递归上都有三个步骤：
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; }
