题解 | #树的子结构#

/*
struct TreeNode {
int val;
struct TreeNode left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};/
class Solution {
public:
int depth(TreeNode *node)
{
if(node==NULL) return 0;
return 1+max(depth(node->left),depth(node->right));
}
int isSame(TreeNode *pRoot1,TreeNode *pRoot2)
{
if(pRoot2==NULL) return 1;
if(pRoot1==NULL && pRoot2!=NULL) return 0;
if(pRoot1->val!=pRoot2->val) return 0;
return isSame(pRoot1->left, pRoot2->left) && isSame(pRoot1->right, pRoot2->right);
}
bool isHashSubtree(TreeNode *pRoot1,TreeNode *pRoot2)
{
int depleng=depth(pRoot2);
queue<TreeNode *> q;
q.push(pRoot1);
while(!q.empty())
{
int len=q.size();
for(int i=0;i<len;i++)
{
TreeNode *temp=q.front();
q.pop();
if(temp->val==pRoot2->val && depth(temp)>=depleng);
{
int a=isSame(temp, pRoot2);
if(a)
{
return true;
}

}
if(temp->left)
{
q.push(temp->left);
}
if(temp->right)
{
q.push(temp->right);
}

        }
    }
    return false;

}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    if(pRoot1==NULL || pRoot2 ==NULL) return false;
    return isHashSubtree(pRoot1, pRoot2);

}

};