题目:输入两棵二叉树A和B,判断B是不是A的子结构。
二叉树节点定义如下:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
求子树的思路大概是这样的:
1.判断树A和树B是否有相同的根节点
2.如果存在则判断A的子树是是否和B的结构相同
3. 如果不存在则A继续向下遍历,重复步骤1,2
第一步递归遍历A树,查找与B数的根元素相同的结点:
bool HasSubtree(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2)
{
bool result=false; if(pRoot1!=NULL&&pRoot2!=NULL)
{
if(pRoot1->m_nValue==pRoot2->m_nValue)
result=DoestTree1HaveTree2(pRoot1,pRoot2);
if(!result)
result=HasSubtree(pRoot1->m_pLeft,pRoot2);
if(!result)
result=HasSubtree(pRoot1->m_pRight,pRoot2);
}
return result;
}
第二部同样递归判断A中的以某个节点为根节点的子树是不是和树B具有相同的结构
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(m_pRoot1->m_pRight,pRoot2->m_pRight);
}