题解 | #树的子结构#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <cstddef>
class Solution {
public:
	bool res = false;
	bool myIsSubtree(TreeNode* p1, TreeNode* p2){
		// 要求初始传入进来的p2一定是不能为空的
		if(!p1 && !p2){
			return true;
		}
		
		if(p1 == NULL && p2!=NULL){
			return false;
		}
		
		if(p1!=NULL && p2==NULL){
			return true;
		}
		if(p1->val!=p2->val){
			return false;
		}
		return myIsSubtree(p1->left, p2->left) && myIsSubtree(p1->right, p2->right);
	}

	void preOrder(TreeNode* p1, TreeNode* p2){
		if(p1 == NULL){
			return;
		}
		if(res){
			return;
		}
		res = myIsSubtree(p1, p2);
		cout<<"res is "<<res<<endl;
		if(res){
			cout<<"here"<<endl;
			return;
		}
		preOrder(p1->left, p2);
		preOrder(p1->right, p2);
	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		//空树不是任意一个棵树的子结构
		if(pRoot2 == NULL){
			return false;
		}
	  	// 没有树是空树的子结构
		if(pRoot1 == NULL){
			return false;
		}
		preOrder(pRoot1, pRoot2);
		cout<<"final res is"<<res<<endl;
		return res;
    }
};