递归问题的解题思路
1.首先,相信函数的作用
将一个函数看成一个整体,而不是试图理解这个递归函数的过程!!!!!!!
比如这题的hasSubtree函数,你只需要相信它能返回一个bool来说明
以当前pRoot2为根的树是否是pRoot1为根的树的一个子结构.
2.其次找到递归基
所谓的递归基 就是递归函数的终止条件,
没有它 递归函数就会无限的自我调用
还是以hasSubtree函数为例子,
hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
这个递归函数调用到最后一定会出现 pRoot1 为null的情况,你需要以此作为终止条件并处理这个情况
显然当A为null时说明 不存在子结构B,返回false 即可;
整理下本题的思路
- 判断树A中以R为根节点的子树是不是包含和树B一样的结构,且我们从根节点开始匹配;
- 遍历树A中的所有非空节点R;
bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
//第一个if中!pRoot2是题目要求的
if (!pRoot1 || !pRoot2) return false;
if (isSame(pRoot1, pRoot2)) return true;
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}
写代码的顺序一般是 第二个if先写,然后return 最后补充递归基
完整代码如下
C++ 代码
/**
* 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 hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if(!pRoot1 || !pRoot2) return false;
if(isSame(pRoot1, pRoot2)) return true;
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}
bool isSame(TreeNode* A, TreeNode* B) {
//递归基 1.当递归到最后时 只会出现两种情况 1.A节点为空 2.B节点为空
//当B 为空的时候 说明前面的都相同了 返回return true
//当A 为空 B不为空的时候说明 A与B不能匹配(因为没有A可以继续匹配了啊!) 返回false
if(!B) return true;
if (!A) return false;
//两个树 相等的条件 1.根节点相同 2.左子树相同 3.右子树相同
if (A->val != B->val) return false;
return isSame(A->left, B->left) && isSame(A->right, B->right);
}
};
确实,要相信函数的作用