题解 | #树的子结构#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
//使用层次遍历的方法
//三个栈
//1.层次遍历主树
//2.判断是否与子树根节点相同
//3.如果相同，则用两个栈判断是否接下来也相同
//4.层次遍历子树，层次遍历主树中子树，一旦不相同，解除小循环
//(递归比栈循环遍历更快捷)
//使用递归的方法
//1.递归寻找相同的根节点
//1.3如果根节点为空，就返回 false(两个根都是)
//1.1如果相同，就递归比较,如果比较为true，就返回true
//1.2如果不同，就去左子树和右子树找

//2.递归比较树
//2.1如果子树为空，返回true
//2.2如果主树为空，返回false
//2.3如果两个节点相等，去左子树和右子树比较
//2.4如果不相等，返回false
#include <cstddef>
class Solution {
	bool IsEqualTree(TreeNode* pRoot1, TreeNode* pRoot2){
		bool result;
		if(pRoot2 == nullptr)
		{
			return true;
		}
		if(pRoot1 == nullptr)
		{
			return false;
		}
		if(pRoot1 -> val == pRoot2 -> val)
		{
			result = IsEqualTree(pRoot1->right, pRoot2->right)&&IsEqualTree(pRoot1->left, pRoot2->left);
			return result;
		}
		else 
		{
			return false;
		}
	}
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if(pRoot1 == nullptr or pRoot2 == nullptr)
		{
			return false;
		}
		if((pRoot1 -> val == pRoot2 -> val)&&(IsEqualTree(pRoot1,pRoot2)))
		{
			return true;
		}
		else 
		{
			return HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
		}
		
    }
};