牛客3732题：二叉树子结构的判断

6个月前 (08-28)牛客题解249

一、问题背景与定义

在二叉树相关算法中，判断一棵树是否是另一棵树的子结构是一个常见且实用的问题。根据题目定义，我们需要判断树B是否是树A的子结构，其中空树不被认为是任何树的子结构。

子结构的定义：树B是树A的子结构，意味着在树A中存在某个节点，以该节点为根的子树与树B在结构和节点值上完全一致。注意这与"子树"概念有所不同，子结构不要求必须从叶子节点开始匹配。

二、算法思路解析

解决这个问题可以采用递归解法：

主函数HasSubtree：

当前pRoot1节点开始的子树是否匹配pRoot2
pRoot2是否在pRoot1的左子树中
pRoot2是否在pRoot1的右子树中

处理边界条件：如果pRoot1或pRoot2为空树，直接返回false
检查三种可能性：
这三种情况满足任意一种即可返回true

辅助函数isSame：

B为空：表示B已经匹配完成
A为空但B不为空：匹配失败
节点值不相等：匹配失败

递归判断两棵树是否相同
递归终止条件：
递归检查左右子树是否都匹配

三、完整代码与注释

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
  private:
    /**
     * 判断两棵树是否相同(递归实现)
     * @param A 树A的节点
     * @param B 树B的节点
     * @return bool 是否相同
     */
    bool isSame(TreeNode* A, TreeNode* B) {
        // B为空表示B树已经匹配完成
        if (B == nullptr) return true;
        // A为空但B不为空，匹配失败
        if (A == nullptr) return false;
        // 当前节点值不相等，匹配失败
        if (A->val != B->val) return false;

        // 递归检查左右子树
        return isSame(A->left, B->left) && isSame(A->right, B->right);
    }
  public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (pRoot1 == nullptr || pRoot2 == nullptr) return false;

        // 三种情况满足一种即可：
        // 1. 以pRoot1为根节点的子树包含pRoot2
        // 2. pRoot2在pRoot1的左子树中
        // 3. pRoot2在右子树中
        return isSame(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) ||
               HasSubtree(pRoot1->right, pRoot2);
    }
};