面试题26-树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节点的定义如下：

struct BinaryTreeNode
{
	double m_dbValue;
	BinaryTreeNode * m_pLeft;
	BinaryTreeNode *m_pRight;
	BinaryTreeNode(int x) :m_dbValue(x), m_pLeft(NULL), m_pRight(NULL){} // 初始化当前结点值为x,左右子树、父节点为空
};

要查找树A中是否存在和树B结构一样的子树，我们可以分为两步：第一步在树A中找到和B的根节点的值一样的节点R，第二步再判断树A中以R为根节点的子树是不是包含和树B一样的结构。
由于递归的代码实现比较简洁，面试时如果没有特别要求，那么我们通常采用递归的方式。

bool HasSubtree(BinaryTreeNode *pRoot1, BinaryTreeNode*pRoot2)
	{
		bool result = false;
		if (pRoot1 != nullptr && pRoot2 != nullptr)
		{
			if(Equal(pRoot1->m_dbValue,pRoot2->m_dbValue))
				result=DoesTree1HaveTree2(pRoot1,pRoot2);
			if (!result)
				result = HasSubtree(pRoot1->m_pLeft, pRoot2);
			if (!result)
				result = HasSubtree(pRoot1->m_pRight, pRoot2);
		}
		return result;
	}
	bool Equal(double num1, double num2)
	{
		if (num1 - num2 > -0.0000001&&num1 - num2 < 0.0000001)
			return true;
		else
			return false;
	}
	bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode*pRoot2)
	{
		if (pRoot2 == nullptr)
			return true;
		if (pRoot1 == nullptr)
			return false;
		if (!Equal(pRoot1->m_dbValue, pRoot2->m_dbValue))
			return false;
		return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft)
			&& DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
	}

1. 功能测试（树A和树B都是普通的二叉树；树B是或者不是树A的子结构）
2. 特殊输入测试（两棵二叉树的一个或者两个根节点为nullptr指针；二叉树的所有节点都没有左子树或者右子树）