AcWing 37. 树的子结构
原题链接
简单
作者:
daniellee
,
2019-04-10 21:11:20
,
所有人可见
,
阅读 972
/**
* 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:
vector<TreeNode*> v;
void dfs(TreeNode* p,int key){
if(p!=NULL){
if (p->val == key){
v.push_back(p);
}
dfs(p->left,key);
dfs(p->right,key);
}
}
bool dfs_c(TreeNode* s,TreeNode* p){
if (s==NULL && p!=NULL) return false;
else if(p==NULL) true;
if (s!=NULL && p!=NULL){
// cout<<s->val <<" "<<p->val<<endl;
if (s->val != p->val){
return false;
}
else{
return dfs_c(s->left,p->left) && dfs_c(s->right,p->right);
}
}
}
bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (pRoot1==NULL || pRoot2 == NULL) return false;
dfs(pRoot1,pRoot2->val);
for(int i=0;i<v.size();i++){
//cout<<v[i]->left->val<<endl;
if (dfs_c(v[i],pRoot2)) return true;
}
return false;
}
};