劍指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;
    }
};