题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

实现如下：

//分两步
//第一步：寻找与B树根节点val相等的A树节点。如果找到进入第二步，否则继续寻找，直到找完A树
//第二步：以找的节点作为A树子树的根节点，同时遍历两棵树，判断是否所有节点都相同
//特殊情况：
//1.进行第二步时注意有可能存在B树大小等于A的子树、B树大小小于A的子树、B树大小大于A的子树
//2.注意对无效值的防御
//3.减少递归此数，及时判断return
/*
struct TreeNode 
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Solution 
{
public:
	//第二步
	bool Subtree(TreeNode* pRoot1, TreeNode* pRoot2)
	{
		if (pRoot1 == NULL && pRoot2 == NULL) return true;//B树大小等于A的子树
		if (pRoot1 != NULL && pRoot2 == NULL) return true;//B树大小小于A的子树
		if (pRoot1 == NULL && pRoot2 != NULL) return false;//B树大小大于A的子树
		if (pRoot1->val == pRoot2->val)//如果val相等则进行进一步比较
			return Subtree(pRoot1->left, pRoot2->left) &&
					 Subtree(pRoot1->right, pRoot2->right);
		else//否则直接return
			return false;
	}
	//第一步
	bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
	{
		//对空指针防御
		if (pRoot1 == NULL || pRoot2 == NULL) return false;
		TreeNode *p1 = pRoot1;
		bool flag = false;//是否相等标志

		if (p1->val == pRoot2->val)//若A树有节点val等于B树根节点val，进入第二步
		{
			flag = Subtree(p1, pRoot2);//开始第二步递归调用
			if (flag) return flag;//如果是子结构，直接return
		}
		//否则继续第一步
		flag = HasSubtree(p1->left, pRoot2);//对左子树进行第一步
		if (flag) return flag;
		flag = HasSubtree(p1->right, pRoot2);//对右子树进行第一步
		if (flag) return flag;
		return flag;
	}
};