题解 | #树的子结构#

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

递归方法：主要是要考虑好退出条件

1.空树不为任意树的子结构，所以pRoot2空时返回false

2.pRoot1为空时，必定返回false

3.当前节点相等时，递归判断左右子树

4.当前节点不等时，保留完整pRoot2结构，从pRoot1的左右子树中递归寻找