如何利用lessThanTree函数判断一棵二叉树所有值小于另一棵

首先，咱们先明确核心需求：要判断t1的所有节点值都小于t2的所有节点值，本质上就是要确保t1里的每一个值都满足「小于t2的所有值」——而这正好可以复用你已经实现的lessThanTree函数。

完整递归实现代码 #

public static boolean treeLessThanTree(BinNode<Integer> t1, BinNode<Integer> t2) {
    // 处理边界情况：如果t2是空树，只有t1也为空时才返回true
    if (t2 == null) {
        return t1 == null;
    }
    // 基准情况：空树t1自然满足条件
    if (t1 == null) {
        return true;
    }
    // 三个条件必须同时满足：
    // 1. 当前t1节点的值小于t2所有值
    // 2. t1左子树的所有值都小于t2所有值
    // 3. t1右子树的所有值都小于t2所有值
    return lessThanTree(t2, t1.getValue()) 
        && treeLessThanTree(t1.getLeft(), t2) 
        && treeLessThanTree(t1.getRight(), t2);
}

代码逻辑解释 #

1. 边界情况处理：
   • 如果t2是空树，那只有当t1也为空时，才返回true（空集的所有元素满足任何条件）；如果t1非空，直接返回false——毕竟t2没有任何值，不存在「t1的值都小于t2所有值」的可能。
   • 如果t1是空树，直接返回true，因为空树里没有任何节点，自然符合要求。
2. 递归逻辑：
   • 对于t1的每个节点，先用lessThanTree(t2, t1.getValue())判断当前值是否小于t2的所有值（这完全匹配lessThanTree的定义：当传入的value小于目标树所有值时返回true）。
   • 接着递归检查t1的左、右子树，确保子树的所有节点也满足同样的条件。
   • 只有当所有条件都满足时，整个函数才返回true。

性能优化方案 #

上面的实现虽然正确，但如果t1节点很多，会对每个节点调用一次lessThanTree，效率较低。其实我们可以换个思路：只要t1的最大值小于t2的所有值，就意味着t1的所有值都小于t2的所有值。基于这个思路，我们可以先找到t1的最大值，再调用一次lessThanTree即可：

// 辅助函数：找到二叉树的最大值
private static int findMax(BinNode<Integer> node) {
    if (node == null) {
        throw new IllegalArgumentException("Empty tree has no maximum value");
    }
    int maxVal = node.getValue();
    // 递归找左子树最大值
    if (node.getLeft() != null) {
        maxVal = Math.max(maxVal, findMax(node.getLeft()));
    }
    // 递归找右子树最大值
    if (node.getRight() != null) {
        maxVal = Math.max(maxVal, findMax(node.getRight()));
    }
    return maxVal;
}

// 优化后的treeLessThanTree
public static boolean treeLessThanTree(BinNode<Integer> t1, BinNode<Integer> t2) {
    if (t1 == null) {
        return true;
    }
    if (t2 == null) {
        return false;
    }
    int t1Max = findMax(t1);
    return lessThanTree(t2, t1Max);
}

这个优化版本只需要调用一次lessThanTree，性能会好很多，尤其是当t1规模较大时。

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