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

二叉树子结构匹配指b的结构（含节点值）在a中以相同拓扑方式出现，不要求b占据a的完整子树；而子树匹配要求从某节点起整棵子树完全一致。

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

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

子结构匹配 ≠ 子树匹配。子树要求从某个节点开始，**整棵子树完全一致**；而子结构只要求目标树的结构（含值）在原树中以相同拓扑方式出现，不要求该节点是叶子或完整子树——比如 target 可能只是原树某分支的“一部分”，其下方还可延伸其他节点。

典型场景：判断 B 是否为 A 的子结构，B 的根节点值必须在 A 中某处出现，且从该点出发，B 的每个非空节点都能在 A 对应位置匹配（B 的空节点不约束 A）。

核心逻辑：两层递归怎么写才不漏判

必须用两个函数配合：isSubStructure 负责在 A 中逐个尝试匹配起点；doesMatch（或类似名）负责从当前节点开始，严格校验 B 是否能“嵌入”进去。

isSubStructure(A, B)：先判边界——若 A 或 B 为空，直接返回 false（注意：B 为空按题意不合法，不能算子结构）；否则尝试三路：当前节点匹配 + 左子树递归 + 右子树递归，用 || 连接
doesMatch(A, B)：这是关键。仅当 B == nullptr 时返回 true（B 已匹配完）；若 A == nullptr 但 B != nullptr，说明 A 提前结束，返回 false；否则比较值，并递归检查左右子树

错误写法常见于把两层逻辑混在一个函数里，导致一旦某次匹配失败就终止整个搜索——漏掉其他可能的起点。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

边界条件和空指针怎么处理才安全

最容易崩的是对 nullptr 的判断顺序。必须保证访问 val 或子节点前，指针已非空。

在 doesMatch 中，先判 B == nullptr → true；再判 A == nullptr → false；最后才用 A->val == B->val
isSubStructure 开头必须判 A == nullptr || B == nullptr，因为题目约定空树不是任何树的子结构
不要用 !A 替代 A == nullptr，虽等价但可读性差，易在复杂条件中出错

示例片段：

bool doesMatch(TreeNode* A, TreeNode* B) {
    if (B == nullptr) return true;
    if (A == nullptr) return false;
    if (A->val != B->val) return false;
    return doesMatch(A->left, B->left) && doesMatch(A->right, B->right);
}