C++如何实现二叉树的子结构匹配算法（Subtree Match）-C++-PHP中文网

子树匹配要求目标树与原树某子树完全一致，即节点值、结构及递归关系严格相等；子结构匹配则只需目标树是原树中连通的一部分，允许b不占满对应子树（如b为空时直接返回true，而子树匹配要求两端同时为空）。

c++如何实现二叉树的子结构匹配算法（subtree match）

什么是子树匹配，和子结构匹配有什么区别

子树匹配（Subtree Match）要求目标树完全等于某棵子树：节点值、左右子树结构、递归关系都严格一致。而子结构匹配（Substructure Match）允许目标树是原树中“连通的一部分”，但不强制占据整个子树根——比如 isSubtree 函数通常指前者，isSubStructure（剑指 Offer 26）才是后者。

实际写代码前先确认需求：

如果题干说“判断 B 是否为 A 的子树”，用严格子树匹配；
如果说“判断 B 是否为 A 的子结构”，就要允许 B 只匹配 A 中某个向下延伸的连通片段（B 的根不一定对应 A 的某个完整子树根）；
常见坑：把 isSubStructure 错写成只调用一次 sameTree，漏掉对 A 所有节点的遍历尝试。

用 sameTree + DFS 实现 isSubtree（严格子树匹配）

核心思路是：对树 A 每个节点，检查以它为根的子树是否与 B 完全相同。不能只比根节点值，必须递归比结构+值。

关键点：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

sameTree 要处理空指针边界：if (!a && !b) return true; if (!a || !b) return false;；
主函数 isSubtree 在当前节点匹配失败时，要继续递归检查 root->left 和 root->right；
不要提前在根节点值不等时返回 false，因为子树可能在下层；

示例逻辑：

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
  if (!root) return false;
  if (sameTree(root, subRoot)) return true;
  return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}