直接两种递归会超时,还是改成了先判断一下下一层是否满足,不然一直递归下去了
class Solution {
public:
bool backtracking(TreeNode* p1, TreeNode* p2){
if(!p2) return true;
if(!p1) return false;
if(p1->val==p2->val){
if((p1->left&&p2->left&&p1->left->val!=p2->left->val)||(p1->right&&p2->right&&p1->right->val!=p2->right->val)){
return false;
}
return backtracking(p1->left,p2->left)&&backtracking(p1->right,p2->right);
}
return false;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if(!pRoot2||!pRoot1) return false;
if(!backtracking(pRoot1, pRoot2)){
//bool left=HasSubtree(pRoot1->left,pRoot2);
//bool right=HasSubtree(pRoot1->right,pRoot2);
return HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
}
return true;
}
};