dhu oj 树的子结构

题目描述：

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

解题思路：

首先判断A和B是否为空，如果有一个为空则返回false，然后分别对比A和B的根节点是否相同，如果相同则递归判断A的左右子树和B的左右子树是否相同，如果不相同，则递归判断A的左子树和B是否相同，或者A的右子树和B是否相同，直到找到相同的子结构或者A的所有节点都遍历完毕。

时间复杂度为O(n*m)，n为A的节点个数，m为B的节点个数。

参考代码：

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot1 == NULL || pRoot2 == NULL){
            return false;
        }
        bool flag = false;
        if(pRoot1->val == pRoot2->val){
            flag = isSameTree(pRoot1, pRoot2);
        }
        if(!flag){
            flag = HasSubtree(pRoot1->left, pRoot2);
        }
        if(!flag){
            flag = HasSubtree(pRoot1->right, pRoot2);
        }
        return flag;
    }
    bool isSameTree(TreeNode* p1, TreeNode* p2){
        if(p2 == NULL){
            return true;
        }
        if(p1 == NULL){
            return false;
        }
        if(p1->val != p2->val){
            return false;
        }
        return isSameTree(p1->left, p2->left) && isSameTree(p1->right, p2->right);
    }
};