如何递归判断两棵二叉树是否包含完全相同的元素（结构可不同）

本文介绍一种高效、健壮的递归方法，用于判断两棵结构可能不同的二叉树是否包含完全相同的一组元素（无序、去重、不关心拓扑结构），并指出常见实现误区与关键修正要点。

原始代码 problem1Recursive 存在一个根本性误解：它试图以“树1的每个节点能否在树2中被find找到”为逻辑主线，但该函数仅单向遍历树1，且过早返回 true（例如仅根节点存在即终止），既未覆盖树2中是否存在冗余元素，也未保证树1所有节点都被验证——更严重的是，其递归结构 && 要求左右子树同时满足条件，这与“全元素匹配”目标完全相悖。

正确的解法需满足两个核心条件：
✅ 双向完备性：树1中的每个元素必须在树2中存在，且树2中的每个元素也必须在树1中存在；
✅ 结构无关性：不能依赖节点位置或父子关系，而应聚焦于元素集合的等价性。

因此，推荐采用集合归一化 + 递归校验策略。以下是经过验证的专业实现：

private static boolean haveSameElements(Node t1, Node t2) {
    // 空树仅当两者均为空时才视为元素相同
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;

    // 检查 t1.root 是否存在于 t2 中，且 t2.root 是否存在于 t1 中
    // 再递归验证剩余元素（排除已匹
配节点后）
    return find(t2, t1.key) && find(t1, t2.key)
           && haveSameElements(removeFirstOccurrence(t1, t1.key), 
                               removeFirstOccurrence(t2, t2.key));
}

⚠️ 注意：上述方案需配套实现 removeFirstOccurrence(Node root, int key)（返回移除首个匹配节点后的新树根）和健壮的 find(Node root, int key)。但若不允许修改原树或实现删除逻辑复杂，更实用的替代方案是先序列化再比较集合：

private static boolean haveSameElements(Node t1, Node t2) {
    Set set1 = new HashSet<>();
    Set set2 = new HashSet<>();
    collectKeys(t1, set1);
    collectKeys(t2, set2);
    return set1.equals(set2);
}

private static void collectKeys(Node node, Set set) {
    if (node == null) return;
    set.add(node.key);
    collectKeys(node.left, set);
    collectKeys(node.right, set);
}

✅ 优势：简洁、清晰、时间复杂度 O(n+m)，空间复杂度 O(n+m)，天然支持重复值（若业务要求去重）或可通过 Multiset 扩展支持计数匹配。
❗ 前提：节点 key 类型需可哈希（如 Integer），且业务允许使用额外空间。

总结：比较异构二叉树的元素等价性，本质是集合运算问题。避免陷入“逐节点结构匹配”的思维陷阱；优先考虑将树映射为抽象集合（Set 或 Multiset），再利用集合内置的 equals() 完成判定——这既符合问题语义，又大幅提升代码可读性、健壮性与可维护性。