java - 检查二叉树中的所有值是否低于另一棵二叉树中的所有值

Question

我有一个函数 - lessThanTree(BinNode t1, int value) 如果值低于 t1 中的所有值，它返回 true。

现在我有一个任务要使用这个函数并编写另一个函数来接收两个二叉树 (t1,t2) 并在 t1 中的所有值都低于 t2 中的所有值时返回 true。

我写了这段递归代码:

public static boolean treeLessThanTree(BinNode<Integer> t1, BinNode<Integer> t2) {
        if (t1 == null)
            return true;
        return lessThanTree(t2, t1.getValue()) && treeLessThanTree(t1.getLeft(), t2)
                && treeLessThanTree(t1.getRight(), t2);
    }

这行得通吗？

Answer 1

它应该可以工作，但是如果两棵树是二叉搜索树，它会不必要地调用 lessThanTree(t2, t1.getValue()) 和 treeLessThanTree(t1.getLeft(), t2 )。

返回treeLessThanTree(t1.getRight(), t2)就足够了(只要t1.getRight()不为空)，因为最大的元素t1 总是位于右子树中(如果根没有右子树，则位于根中)。

因此，更有效的解决方案是:

public static boolean treeLessThanTree(BinNode<Integer> t1, BinNode<Integer> t2) 
{
    if (t1 == null)
        return true;
    else if (t1.getRight() != null)
        return treeLessThanTree(t1.getRight(), t2);
    else 
        return lessThanTree(t2, t1.getValue());
}