牛客網-樹的子結構

一、題目

二、思路

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);
    }
};