牛客網——樹的子結構（C++）

輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）

C++

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool dfs(TreeNode* root1, TreeNode* root2)
    {
        if(NULL==root1)
        {
            if(NULL==root2)
            {
                return true;
            }
            return false;
        }
        else
        {
            if(NULL==root2)
            {
                return true;
            }
            bool flag=false;
            if(root1->val==root2->val)
            {
                flag=dfs(root1->left,root2->left) && dfs(root1->right,root2->right); 
            }
            if(flag)
            {
                return true;
            }
            else
            {
                return dfs(root1->left,root2) || dfs(root1->right,root2);
            }
        }
    }
    
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(NULL==pRoot2)
        {
            return false;
        }
        return dfs(pRoot1,pRoot2);
    }
};