面试题26：树的子结构

从“根值相同为什么还不够”开始

先预测：树A根为8，左孩子也是8；树B根为8、左孩子为9。A的根值等于B根，但A根的左孩子是8，不是9，所以根位置匹配失败；继续搜索A的左孩子8，若它的左孩子是9，则这个新位置可能成功。

因此判断树的子结构需要两层工作：先定位相同根节点，再从该位置再比较左右子树。值相同只说明它是候选根，并不能证明形状和值都覆盖B。

外层HasSubtree遍历A的每个可能位置；内层DoesTree1HaveTree2从一个候选根开始，同时沿A和B的左、右边检查。这种两个树指针锁步向下的过程称为。

外层搜索与内层匹配不可混成一个空规则

外层收到空A或空B时返回false。空A没有候选位置；作者约定“空树不是任意树的子结构”，所以空B也不是有效查询目标。

内层则恰好相反：当B变为空，表示模板这一分支的所有节点已经匹配完，应返回true，即使A对应位置还继续有子孙。只有B未空而A先空，才说明A不够深并返回false。

这两个“B为空”处于不同语义层：外层判断题目是否提出一棵有效模板，内层判断有效模板的某条分支是否已经完成。为了让双空时内层成功，必须先检查B为空，再检查A为空；交换顺序会把两个分支同时结束误判为失败。

子结构不是完整子树

把B的全部节点和值能在A某个局部一一对应称为。B走到空就完成了自己的约束，A多出的后代不影响成功。

完整子树要求候选A分支与B完全相同；B为空时A也必须为空。两者只差一个终止条件，却表达完全不同的问题。

例如B只有根8和左孩子9，A候选8还多一个右孩子2。本题视为子结构，因为B没有要求右侧必须为空；完整子树比较则失败。需求文档必须明确“包含局部结构”还是“某棵完整子树相等”。

忠实实现作者的双重递归

作者节点值为double，Equal把差值限制在负0.0000001与正0.0000001之间，即严格绝对误差小于1e-7。不是现有页面曾写的1e-8。

struct BinaryTreeNode {
    double value;
    BinaryTreeNode* left = nullptr;
    BinaryTreeNode* right = nullptr;
};
 
bool equalValue(double first, double second) {
    const double difference = first - second;
    return difference > -0.0000001 &&
           difference <  0.0000001;
}
 
bool matchesFrom(BinaryTreeNode* root1,
                 BinaryTreeNode* root2) {
    if (root2 == nullptr) return true;
    if (root1 == nullptr) return false;
    if (!equalValue(root1->value, root2->value)) return false;
 
    return matchesFrom(root1->left, root2->left) &&
           matchesFrom(root1->right, root2->right);
}
 
bool hasSubtree(BinaryTreeNode* root1,
                BinaryTreeNode* root2) {
    bool result = false;
    if (root1 != nullptr && root2 != nullptr) {
        if (equalValue(root1->value, root2->value)) {
            result = matchesFrom(root1, root2);
        }
        if (!result) {
            result = hasSubtree(root1->left, root2);
        }
        if (!result) {
            result = hasSubtree(root1->right, root2);
        }
    }
    return result;
}

外层顺序是当前候选、左子树、右子树，属于先序搜索。找到成功位置后，后续分支不再执行；这种既保持真假结果，也避免继续访问不需要的节点。

内层左右必须使用逻辑与：B的左约束和右约束都要满足。外层三个位置使用逻辑或：当前、左子树、右子树中任一成功即可。把这两个运算混淆，会把“只匹配一侧”误判为完整覆盖。

浮点容差的原书边界与工程升级

作者的是固定绝对阈值1e-7，适合示例量级。差值恰好等于正负1e-7时，因为条件是严格大于与严格小于，结果为false。

固定绝对误差对极大值可能过严，对接近零的值则语义较直观。工程比较常结合绝对容差和相对容差：

#include <algorithm>
#include <cmath>
 
bool nearlyEqual(double first, double second,
                 double absoluteTolerance = 1e-7,
                 double relativeTolerance = 1e-12) {
    if (first == second) return true;
    if (!std::isfinite(first) || !std::isfinite(second)) {
        return false;
    }
    const double difference = std::fabs(first - second);
    const double scale =
        std::max(std::fabs(first), std::fabs(second));
    return difference < absoluteTolerance ||
           difference < relativeTolerance * scale;
}

这段是工程扩展，不应冒充作者源码。它明确处理同号无穷相等、NaN不相等和数值尺度。比较策略会改变“节点值相同”的定义，必须在建树、索引和匹配中保持一致。

若节点值是整数、字符串或业务对象，应注入等价谓词，而不是保留浮点容差。字符串通常按精确值比较；对象可能只比较主键，也可能要求全部字段相等，契约不同会改变候选数量和复杂度。

最坏复杂度从重复候选产生

设A有N个节点，B有M个节点。外层最多访问A的N个候选位置；每个候选值与B根相同且局部匹配到很深才失败时，内层可能检查O(M)节点，总时间最坏O(NM)。

典型最坏例是两棵退化链，所有节点值都相同，而B最后一个位置与A对应值或方向不同。A的许多起点都会触发接近完整的B匹配。若根值分布稀疏，只有少数候选进入内层，实际工作接近O(N)加匹配成本，但不能把平均值无条件写成O(N)。

外层递归深度最多是A高度hA，内层最多是B高度hB；一次候选匹配期间两类调用栈叠加，峰值O(hA+hB)。极端斜树可达O(N+M)，平衡树则接近对数高度。

可把外层改为显式栈，避免A的深递归；内层仍可能深。若需要大量重复查询，可为树做结构哈希或序列化加空标记，但浮点近似相等不满足简单精确哈希，优化前要重新定义等价关系。

容差相等还可能不具传递性：a与b差一点、b与c差一点都在阈值内，a与c却可能超过阈值。它适合一次局部比较，却不适合作为无序集合键或并查集合并规则。若要为候选根建立索引，应先把数值量化到明确区间，或使用业务提供的离散ID；否则索引筛掉的候选可能与逐点比较结果不一致。

批量查询时可以为每个A节点缓存“值加左右结构”的精确签名，先快速排除不可能候选，再用原算法确认。但子结构允许A在B叶端继续延伸，不能直接拿完整子树哈希判等；签名必须支持模板通配结束，或只作为否定过滤器。优化若改变空分支语义，就不再是同一道题。

当A高度很大而B较小，可用显式栈遍历候选，并让内层使用成对节点栈，彻底避免系统递归栈。迭代版仍要保持“B空成功、A先空失败、左右都匹配”的顺序；控制流改写不能改变逻辑边界。

树结构、图结构与共享节点

算法假设A和B都是有限无环二叉树。若孩子指针形成环，递归不会终止；若同一节点被多个父节点共享，结构实际是有向无环图，函数可能重复访问同一子图，复杂度分析也会变化。

对不可信结构可先检测环，或由拥有容器保证树不变量。unique_ptr左右孩子自然表达唯一所有权树；测试中使用裸指针时，销毁函数也必须避免共享节点重复释放。

算法只读节点，不修改结构，适合并发只读；但若另一线程同时替换孩子或销毁节点，仍会数据竞争和悬空。不可变树、读锁或生命周期快照才是完整保证。

返回bool不暴露匹配位置。若产品需要展示证据，可返回第一个候选根指针，或收集全部匹配根；后者不能在第一次成功后短路，时间和内存都要重新评估。

作者九组测试怎样覆盖形状

Test1在普通分叉树中成功，B为8的左右孩子9和2；Test2把A对应2改成3，验证值冲突失败。Test3和Test4是只有左孩子的斜树，分别验证匹配与末端值不同。

Test5是只有右孩子的匹配斜树；Test6让B在某层多出左孩子3，而A只有右链，验证方向和缺失分支失败。Test7到Test9分别是A空、B空、两者都空，全部返回false。

自动测试应断言九组结果，并单独检查容差边界：

#include <cassert>
 
void testSubstructure() {
    BinaryTreeNode a9{9};
    BinaryTreeNode a2{2};
    BinaryTreeNode aLeft8{8, &a9, &a2};
    BinaryTreeNode a7{7};
    BinaryTreeNode aRoot8{8, &aLeft8, &a7};
 
    BinaryTreeNode b9{9};
    BinaryTreeNode b2{2};
    BinaryTreeNode b8{8, &b9, &b2};
 
    assert(hasSubtree(&aRoot8, &b8));
    b2.value = 3;
    assert(!hasSubtree(&aRoot8, &b8));
    b2.value = 2;
 
    assert(!hasSubtree(nullptr, &b8));
    assert(!hasSubtree(&aRoot8, nullptr));
    assert(!hasSubtree(nullptr, nullptr));
 
    assert(equalValue(1.0, 1.0 + 0.00000005));
    assert(!equalValue(1.0, 1.0 + 0.0000002));
}

还应构造B叶节点对应A有额外孩子的案例，确认子结构成功；再用完整子树函数对同一案例断言失败。这样能直接锁定B为空时的终止语义。

树值重复时，测试要确保第一个候选失败后外层继续搜索后续同值候选。只测试根位置成功会掩盖错误的“匹配一次失败就直接返回false”实现。

正确性证明

内层按B节点数归纳。B为空时所有约束已满足；B非空而A为空或值不同必失败；值相同且两侧模板都能匹配时，当前B整棵结构被A覆盖。因此matchesFrom准确判断固定候选。

外层对A做先序遍历。当前候选匹配、左子树存在候选、右子树存在候选三种可能覆盖A全部节点；逻辑或在任一成功时返回true，全部失败才返回false。因此hasSubtree存在且仅存在某候选能覆盖B时成功。

外层对空B返回false落实题目约定。结合内层正确性、候选覆盖完整性和终止条件，算法对有限无环二叉树返回正确答案。

本章练习

本章回顾

1. 树的子结构需要外层先定位相同根节点，内层再比较左右子树。
2. 候选根值相同只是启动条件，不代表局部形状已经匹配。
3. 外层空B返回false，内层B耗尽返回true，两个语义不能混用。
4. 子结构允许A在B结束处继续有后代，完整子树不允许。
5. 作者double比较使用严格绝对差小于1e-7。
6. 外层当前、左、右用逻辑或，内层左右对应分支用逻辑与。
7. 最坏时间O(NM)，递归栈峰值O(hA+hB)。
8. 九组官方测试覆盖分叉树、左右斜树、结构缺口和空树。

名词解释