递归比较结构不同的二叉树元素一致性遇问题求助

嘿，我来帮你梳理下当前代码的问题，然后一步步搞定这个“判断两棵二叉树是否包含完全相同元素（不管结构）”的需求～

先说说你当前代码的核心问题 #

你的思路方向是对的（递归遍历+检查元素存在），但几个关键逻辑没处理好：

1. 终止条件错误：当t1或t2为null时直接返回false，但如果两棵树都为空，它们的元素集合是相等的，应该返回true；如果只有一棵树为空，才返回false。
2. 分支逻辑漏洞：你写的else if(find(t2, t1.key)) { return true; }会导致只要当前节点的元素在t2中，就直接返回true，完全跳过了对左右子树的检查——这意味着只要有一个元素匹配就返回成功，而不是所有元素都匹配。
3. 缺少反向验证：你的代码只检查了t1的元素是否都在t2中，但没检查t2的元素是否都在t1中。比如t1是{1,2}，t2是{1,2,3}，你的代码会错误返回true，但实际上两者元素集合并不相等。

修正后的递归实现方案 #

我们需要先实现一个单向检查辅助函数：验证一棵树的所有元素都存在于另一棵树中，然后在主函数里双向调用这个辅助函数，确保两棵树的元素完全互相包含。

代码实现 #

// 辅助函数：检查source树的所有元素都存在于target树中
private static boolean allElementsExist(Node source, Node target) {
    if (source == null) {
        // 源树已经遍历完，没有更多元素需要检查，返回true
        return true;
    }
    if (target == null) {
        // 源树还有元素，但目标树为空，肯定不存在，返回false
        return false;
    }
    // 先检查当前节点的key是否在目标树中
    if (!find(target, source.key)) {
        return false;
    }
    // 递归检查左右子树的所有元素都在目标树中
    return allElementsExist(source.left, target) && allElementsExist(source.right, target);
}

// 主函数：双向检查确保元素集合完全相等
private static boolean problem1Recursive(Node t1, Node t2) {
    return allElementsExist(t1, t2) && allElementsExist(t2, t1);
}

考虑重复元素的进阶方案 #

如果你的二叉树中存在重复的key（比如t1有两个1，t2只有一个1），上面的方案会误判为相等。这时候我们需要统计每个元素的出现次数，再比较次数是否一致：

private static void countElementFrequency(Node node, Map<Integer, Integer> frequencyMap) {
    if (node == null) {
        return;
    }
    // 更新当前key的出现次数
    frequencyMap.put(node.key, frequencyMap.getOrDefault(node.key, 0) + 1);
    // 递归遍历左右子树
    countElementFrequency(node.left, frequencyMap);
    countElementFrequency(node.right, frequencyMap);
}

private static boolean problem1Recursive(Node t1, Node t2) {
    Map<Integer, Integer> freq1 = new HashMap<>();
    Map<Integer, Integer> freq2 = new HashMap<>();
    
    countElementFrequency(t1, freq1);
    countElementFrequency(t2, freq2);
    
    // 比较两个频率映射是否完全一致
    return freq1.equals(freq2);
}

这个方案虽然没有用递归直接比较，但递归用于遍历统计，同样符合你的递归思路，而且能正确处理重复元素的场景。

内容的提问来源于stack exchange，提问作者Melons