如何识别二叉树的“亲戚”？——探秘判断子树的奥妙

在这里插入图片描述

本篇博客会讲解力扣“572. 另一棵树的子树”的解题思路，这是题目链接。先来审题：

在这里插入图片描述
本题的思路是：使用递归，把大问题化作小问题。

先来思考：如何判断q是不是p的子树呢？

q是p的子树有3种情况，分别是：

q和p相同。
q是p的左子树的子树。
q是p的右子树的子树。

其中，还要讨论一些特殊情况，也就是递归的终止条件。

p为空，q非空，显然q不是p的子树。
p非空，q为空，显然q是p的子树，不过这一点不用单独讨论。
p和q都为空，显然q是p的子树，不过这一点不用单独讨论，后面判断2棵树是否相同时，2棵空树是相同的。

对于判断q是不是p的左子树和右子树的子树这个问题，就是很简单的递归调用。那么问题就转换成了如何判断2棵树相同，这又是另一个经典问题了。

如何判断2棵树p和q相同呢？p和q相同必须同时满足以下3点：

根节点的值相同。
p的左子树和q的左子树相同。
p的右子树和q的右子树相同。

其中，还要讨论一些特殊情况，也就是递归的终止条件。

p为空，q为空，此时2棵树相同。
p和q中，其中一棵树为空，另一棵非空，2棵树不相同。

理解了以上几点，就可以写代码了。

// 判断2棵树是否相同
bool IsSameTree(struct TreeNode* p, struct TreeNode* q)
{
    // 2棵树都是空树
    if (p == NULL && q == NULL)
    {
        return true;
    }

    // 1棵树是空树，另一棵非空
    if (p == NULL || q == NULL)
    {
        return false;
    }

    // 2棵树相同当且仅当值相同，左右子树分别相同
    return p->val == q->val
        && IsSameTree(p->left, q->left)
        && IsSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    // 非空树不是空树的子树
    if (root == NULL && subRoot)
    {
        return false;
    }

    // 先判断2棵树是否相同
    // 再判断是不是左子树和右子树的子树
    return IsSameTree(root, subRoot)
        || isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}