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

题目：

输入两棵二叉树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;
    }
};