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

霞舞 2025-12-31 00:00:00 次阅读

本文介绍一种不依赖树形结构的递归方法，用于判断两棵二叉树是否包含完全相同的一组节点值，适用于结构不同但元素集合等价的场景。

要解决“两棵结构不同的二叉树是否包含相同元素”这一问题，关键在于：我们不比较树的形状或父子关系，而是验证两棵树的节点值集合是否完全相等（即互为子集）。原始代码 problem1Recursive 存在根本性逻辑偏差——它仅单向检查 t1 的每个节点是否存在于 t2 中，且递归方式错误（如 && 连接左右子树会导致过早失败），既未覆盖 t2 到 t1 的反向验证，也无法处理重复值或集合完整性。

✅ 正确思路应为：

双向集合等价性检验：t1 的所有元素 ∈ t2，且 t2 的所有元素 ∈ t1；
避免暴力嵌套搜索（如对每个 t1 节点调用 find(t2, key)），否则时间复杂度高达 O(n×m)，易超时；
推荐方案：先中序遍历两树得到有序列表 → 比较列表是否相等（简洁、健壮、易调试）。

以下是高效、可读性强的完整实现：

import java.util.*;

// 辅助方法：中序遍历获取所有节点值（升序，便于后续比较）
private static List inorderValues(Node root) {
    List list = new ArrayList<>();
    inorderHelper(root, list);
    return list;
}

private static void inorderHelper(Node node, List list) {
    if (node == null) return;
    inorderHelper(node.left, list);
    list.add(node.key); // 假设 key 为 Integer 类型
    inorderHelper(node.right, list);
}

// 主方法：判断两树元素集合是否完全相同
private static boolean haveSameElements(Node t1, Node t2) {
    List vals1 = inorderValues(t1);
    List vals2 = inorderValues(t2);

    // 长度不同直接返回 false
    if (vals1.size() != vals2.size()) return false;

    // 排序后逐个比较（若中序已有序可省略排序，但为鲁棒性建议显式排序）
    Collections.sort(vals1);
    Collections.sort(vals2);

    return vals1.equals(vals2);
}

⚠️ 注意事项：

若树中允许重复值，上述基于 List 的方案天然支持（无需去重）；若要求忽略重复只比集合，请改用 TreeSet 或 HashSet（但需注意：HashSet 不保序，比较前需转为 List 并排序）。
若节点值类型非 Integer，请确保其 equals() 和 hashCode() 实现正确，或自定义比较器。
时间复杂度：O(n + m)（遍历） + O(n log n + m log m)（排序），空间复杂度：O(n + m)。
原答案中提供的单向递归解法（含 || 分支）逻辑错误：它实际在检测“t1 的某条路径是否能覆盖 t2 全部节点”，既不充分也不必要，不可用于集合等价性判定，请勿采用。