题解 | #树的子结构#

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        // 空树不是任意一个数的子结构
        // 递归终止条件：1.当pRoot2 为空节点直接返回false. 2.当pRoot1递归到空节点时返回false；
        if(!pRoot1 || !pRoot2)    return false;

        // 两重递归；
        return dfs(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
    }

    bool dfs(TreeNode* p, TreeNode* q){
        // 当q节点为空时，p节点可以不为空，这求的是子结构而不是子树；
        if(!q)    return true;
        if(!p || p->val != q->val)    return false;

        return dfs(p->left, q->left) && dfs(p->right, q->right);
    }
};