本文介绍一种递归方法，用于判断两棵结构可能不同的二叉树是否包含完全相同的一组节点值，不依赖形状匹配，仅关注元素集合等价性。
在实际开发中，我们常需比较两棵二叉树的元素内容一致性，而非结构一致性。例如：一棵是平衡BST，另一棵是退化为链表的BST，只要它们存储的键值集合完全相同（无重复、顺序无关），就应判定为“元素相等”。原始代码 problem1Recursive 存在逻辑偏差——它仅单向检查 t1 的每个节点是否存在于 t2 中，且终止条件错误（null 时返回 false 会过早中断），并未验证双向集合包含关系。
正确解法需满足：
✅ t1 的所有节点值均在 t2 中出现；
✅ t2 的所有节点值也均在 t1 中出现；
✅ 值唯一（无重复键），否则需改用计数哈希表等扩展方案。
以下是推荐的递归实现（基于双向存在性验证）：
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 中
if (!find(t2, t1.key) || !find(t1, t2.key)) {
return false;
}
// 递归检查左右子树 —— 注意：此处仍需完整遍历两棵树的所有节点
// 更健壮的做法是先收集元素再比较（见下方优化建议）
return haveSameElements(t1.left, t2)
&& haveSameElements(t1.right, t2)
&& haveSameElements(t2.left, t1)
&& haveSameElements(t2.right, t1);
}⚠️ 但上述纯递归方案存在指数级时间开销（重复调用 find 导致大量冗余搜索）。生产环境更推荐以下高效两步法：
-
提取元素集合（中序/任意遍历）：
private static Set<Integer> collectKeys(Node root) { Set<Integer> set = new HashSet<>(); collectKeysHelper(root, set); return set; } private static void collectKeysHelper(Node node, Set<Integer> set) { if (node == null) return; set.add(node.key); collectKeysHelper(node.left, set); collectKeysHelper(node.right, set); } -
直接比较集合：
private static boolean haveSameElements(Node t1, Node t2) { return collectKeys(t1).equals(collectKeys(t2)); }
✅ 时间复杂度：O(n + m)，空间复杂度：O(n + m)；
✅ 自动处理空树、单节点、重复值（若需支持重复，改用 Multiset 或 Map<Integer, Integer> 计数）；
✅ 逻辑清晰、易于测试与维护。
总结：比较树的元素等价性，本质是集合比较问题。避免陷入“结构递归陷阱”，优先考虑抽象为集合操作——既准确又高效。若必须纯递归无额外空间，需确保 find 方法为 O(log n)（如树为BST），并辅以剪枝优化；但一般场景下，显式集合提取是最可靠的选择。
