剑指offer之面试题18：树的子结构

题目：

创新互联是一家网站设计公司，集创意、互联网应用、软件技术为一体的创意网站建设服务商，主营产品：成都响应式网站建设公司、高端网站设计、全网整合营销推广。我们专注企业品牌在网站中的整体树立，网络互动的体验，以及在手机等移动端的优质呈现。成都做网站、成都网站制作、成都外贸网站建设、移动互联产品、网络运营、VI设计、云产品.运维为核心业务。为用户提供一站式解决方案，我们深知市场的竞争激烈，认真对待每位客户，为客户提供赏析悦目的作品，网站的价值服务。

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

思路：

    //1、遍历二叉树pRoot1,找到和pRoot2根结点相等的结点
    //2、在对这个节点进行判断，是否其内部和PRoot2的结构完全相等

代码：

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
    class Solution {
public:
     bool JudgeSub(TreeNode *pRoot1,TreeNode *pRoot2)
    {
        //一定要先判断PRoot2，在判断proot1
        if(pRoot2==NULL)
        {
            return true;
        }
         if(pRoot1==NULL)
        {
            return false;
        }
        if(pRoot1->val==pRoot2->val)
        {
            return JudgeSub(pRoot1->left,pRoot2->left)&&JudgeSub(pRoot1->right,pRoot2->right);
        }
        else
        {
            return false;
        }
    }
    //1、遍历二叉树pRoot1,找到和pRoot2根结点相等的结点
    //2、在对这个节点进行判断，是否其内部和PRoot2的结构完全相等
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result=false;
        if(pRoot1!=NULL&&pRoot2!=NULL)
        {
            if(pRoot1->val==pRoot2->val)
            {
                result=JudgeSub(pRoot1,pRoot2);
            }
            if(!result)
            {
                result=HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
            }
        }
        return result;
    }
};