一、题目链接

https://leetcode.cn/problems/subtree-of-another-tree/submissions/536304222

二、题目思路

1.首先遍历大树，判断大树的根结点的值是否等于小树的根结点的值，如果不相等，就找大树的左孩子或者右孩子，以左孩子为根的结点的，如果等于小树的根结点的值，就调用判断两棵树是否相等的函数
 

2.如果返回值是true就说明小树是大树的子数，直接return true   。 如果不是，就要继续找该结点的左孩子或者右孩子继续判断，不能return false 。直到大树到了空节点时，说明小树不是大树的子树，return false。

3.左右子树之一符合就说明小树是大树的子树

三、题解代码

//判断两棵树是否相等函数
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);
}


//遍历大树的所有结点，判断以当前的结点为根结点的树，是否与小树相等
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
 
   if(root==NULL)//如果大树遍历到空结点，说明小树不是大树的子树
   return false;
     
     //如果当前的根结点和小树的根结点的值相等，就调用判断两颗树是否相等函数
   if(root->val==subRoot->val)   
   {
       if(true==isSameTree(root,subRoot))//如果得到的是true就将结果返回，不是就不要返回
       return true;                       //因为还要判断以接下来的结点为根的树
   }

// 左右子树其中之一成功就说明小树是大树的子树
   return isSubtree(root->left,subRoot) ||isSubtree(root->right,subRoot);
   
}