题解 | #树的子结构#

直接两种递归会超时，还是改成了先判断一下下一层是否满足，不然一直递归下去了

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

            //bool left=HasSubtree(pRoot1->left,pRoot2);
            //bool right=HasSubtree(pRoot1->right,pRoot2);
            return HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
        }
        return true;
    }
};