牛客3732题解：递归分治判断二叉树子树关系
7个月前 (08-07)
一、题目解读
牛客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)（递归栈）。关键在于设计清晰的递归逻辑与边界条件，适用于需要判断树包含关系的场景，体现了递归算法的优雅与高效。
原创内容 转载请注明出处
