口试经典（8）-树的子结构

面试经典（8）--树的子结构

题目描述：输入俩棵二叉树A和B，判定B是不是A的子结构

                 1                                                   8
               /    \                                               /    \
              8    7                                             9    2
            /    \
           9    2
                /  \
               4  7

右边的二叉树是左侧的子结构

算法分析：这个题目是微软2010年的校招题目，使用前序遍历，可以加深对前序遍历的理解。大概思想是：我们前序遍历A，如果当前节点值和B的根节点相同，然后我们判定A是否含B。因此，首先要写一个函数bool subtree(Node *pRoot1,Node *pRoot2);判定以pRoot1为根节点的树是否包含以pRoot2为根节点的树。

代码如下：

bool subtree(Node *pRoot1,Node *pRoot2)
{
	if(pRoot2==NULL)
		return true;
	if(pRoot1==NULL)
		return false;
	if(pRoot1->m_chValue!=pRoot2->m_chValue)
		return false;
	return subtree(pRoot1->m_pLeft,pRoot2->m_pLeft) && subtree(pRoot1->m_pRight,pRoot2->m_pRight);
}

上面代码可谓"精简彪悍"。一是if(pRoot2==NULL)return true必须放在第二个判定条件if(pRoot1==NULL)之前。最后的返回语句相当吊。这用到的一个c语言的一个知识点：比如a<b && c<d，如果a>=b，后边的语句c<d是不会执行的。所以如果左子树返回false，那不会递归调用右子树，这正是我们需要的。

下面开始分析对A树的递归遍历算法。话不多说上图！

上图用来理解正确逻辑（A中包含B），下图是用来理解错误逻辑(A中不包含B)。

代码如下：

bool isSubTree(Node *pRoot1,Node *pRoot2)
{
	if(pRoot2==NULL)
		return false;
	if(pRoot1==NULL)
		return false;
	bool found=false;
	if(pRoot1->m_chValue==pRoot2->m_chValue)
		found=subtree(pRoot1,pRoot2);
	if(!found)
		found=isSubTree(pRoot1->m_pLeft,pRoot2);
	if(!found)
		found=isSubTree(pRoot1->m_pRight,pRoot2);
	return found;
}