牛客3732题解：递归分治判断二叉树子树关系

一、题目解读

牛客3732题要求判断二叉树A是否包含二叉树B作为子树。即是否存在A的某子树与B结构完全相同（节点值、左右子树关系均匹配）。问题核心在于高效搜索A的所有子树并与B进行比对，需避免重复遍历。

二、解题思路

核心思想为：

1. 递归分治：将大问题拆解为小问题，分别判断A的根节点是否等于B的根节点，若相等则递归检查左右子树；

2. 子树匹配：设计isSame函数判断两树是否完全相同，通过递归遍历左右子树并比对节点值；

3. 三种可能性：若A的根节点匹配B，或A的左/右子树包含B，则返回true。

三、解题步骤

1. 主函数HasSubtree：

    输入校验：若A或B为空，直接返回false；

    递归判断三种情况：

        以A为根节点的子树是否与B相同（调用isSame）；

        A的左子树是否包含B；

        A的右子树是否包含B。

2. 辅助函数isSame：

    若B为空，说明B已匹配完成，返回true；

    若A为空但B不空，匹配失败；

    若节点值不相等，失败；

    递归检查A的左右子树是否与B的左右子树匹配。

四、代码与注释

class Solution {
private:
    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);
    }
};

五、总结

本解法通过递归分治将子树匹配问题分解为局部节点比对，时间复杂度O(nm)（n、m为两树节点数），空间复杂度O(n+m)（递归栈）。关键在于设计清晰的递归逻辑与边界条件，适用于需要判断树包含关系的场景，体现了递归算法的优雅与高效。