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

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};

如下图，右边的二叉树是左边二叉树的子结构。

判断的过程如下：第一步，在树A中查找与树B的根节点的值一样的结点，这实际上就是树的遍历。第二步，如果找到了这样的结点，判断树A的这个结点的子树是否和树B具有相同的结构。无论是第一步，还是第二步，都可以用递归的方法求解。下面是示例代码：

bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
bool result = false;

if (pRoot1 != NULL && pRoot2 != NULL)
{
if (pRoot1->m_nValue == pRoot2->m_nValue)
result = DoesTree1HaveTree2(pRoot1, pRoot2);

if (!result)
result = HasSubtree(pRoot1->m_pLeft, pRoot2);

if (!result)
result = HasSubtree(pRoot1->m_pRight, pRoot2);
}

return result;
}

bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
if (pRoot2 == NULL)
return true;

if (pRoot1 == NULL)
return false;

if (pRoot1->m_nValue != pRoot2->m_nValue)
return false;

return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}