题解 | #树的子结构#

• 有一颗树为空，返回false；
• 比较当前子树匹配是否相同，左右子树匹配是否相同；
• 匹配条件：
• 子树为NULL，返回true；
• 主树为NULL或主树值与子树值不相等，返回false；
• 继续比较各自子树。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool compare(TreeNode* root1, TreeNode* root2) {
        if (root2 == NULL) return true;
        if (root1 == NULL || root1->val != root2->val) return false;
        return compare(root1->left, root2->left) && compare(root1->right, root2->right);
    }


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

        return compare(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);

    }
};