牛客网-树的子结构

一、题目

二、思路

1）在HasSubtree中，如果pRoot1nullptr || pRoot2nullptr，直接返回false

2）当pRoot1->val==pRoot2->val时，调用tree函数，进入递归

• tree函数递归条件：如果pRoot2==nullptr，返回true
• 如果pRoot1==nullptr || pRoot1->val!=pRoot2->val，返回false；
• 其余tree(pRoot1->left,pRoot2->left) && tree(pRoot1->right,pRoot2->right)，进入递归

3）如果pRoot1中有多个值和pRoot2根节点值相同，则当根节点相等时，调用tree函数进入判断是否是子树，同时HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2)进行下一个根节点的比较

4）当根节点值不相同时，HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2)进行左、右子树和根节点比较

三、代码

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(pRoot1==nullptr || pRoot2==nullptr)
        {
            return false;
        }
        if(pRoot1->val==pRoot2->val)
        {
            return tree(pRoot1,pRoot2) || HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2);
        }
        else
        {
            return HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2);
        }
    }
    bool tree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot2==nullptr)
        {
            return true;
        }
        if(pRoot1==nullptr || pRoot1->val!=pRoot2->val)
        {
            return false;
        }
        return tree(pRoot1->left,pRoot2->left) && tree(pRoot1->right,pRoot2->right);
    }
};