题解 | #树的子结构#

/*
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(pRoot2 == nullptr)
            return false;
        //一个为空，另一个不为空
        if(pRoot1 == nullptr && pRoot2 != nullptr)
            return false;
        if(pRoot1 == nullptr || pRoot2 == nullptr)
            return true;
        //递归比较
        bool flag1 = recursion(pRoot1, pRoot2); 
        //递归树1的每个节点
        bool flag2 = HasSubtree(pRoot1->left, pRoot2); 
        bool flag3 = HasSubtree(pRoot1->right, pRoot2);
        return flag1 || flag2 || flag3;
    }

    bool recursion(TreeNode* pRoot1, TreeNode* pRoot2) {
		if(!pRoot1 && pRoot2) return false;
		else if(!pRoot2) return true;
		else
		{
			if(pRoot1->val!=pRoot2->val)
				return false;
			return recursion(pRoot1->left, pRoot2->left) && recursion(pRoot1->right, pRoot2->right);
		}
    }
};