题解 | #树的子结构#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
//值得一写 两段递归
class Solution {
public:
	bool IsSameTree(TreeNode* pRoot1,TreeNode* pRoot2){
		if(pRoot2==nullptr){
			return true;
		}//如果此匹配树的点为空，那我们就判定原树

		if(pRoot1==nullptr){
			return false;
		}//这里做出了判断 如果pRoot1为空且pRoot2，说明模式树已经穷尽了，pRoot2还没穷尽
		if(pRoot1!=nullptr&&pRoot2!=nullptr&&pRoot1->val != pRoot2->val){
			return false;
		}
		bool lchild=true;
		bool rchild =true;
		lchild = IsSameTree(pRoot1->left,pRoot2->left);
		rchild = IsSameTree(pRoot1->right,pRoot2->right);
		return lchild && rchild;

	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {


		if (!pRoot1 || !pRoot2) {
			return false;
		}

		if(IsSameTree(pRoot1, pRoot2))
		return true;
		if (HasSubtree(pRoot1->left,pRoot2)) {
			return true;
		}
		if (HasSubtree(pRoot1->right,pRoot2)) {
			return true;
		}
		return false;
    }
};