java - boolean 递归的替代方法

Question

我似乎想不出解决这个问题的方法。至少不是一种优雅的方式。该函数应确定给定树是否为二叉搜索树。它似乎有效(虽然现在不允许重复)。

这是函数开始的地方:

isBinarySearchTree(根)

功能:

public static boolean isBinarySearchTree(Node node) {

    if (node.leftchild != null) {
        if (node.leftchild.key < node.key)
            isBinarySearchTree(node.leftchild);
        else {
            System.out.println("false: " + node + " -> " + node.leftchild);
            return false;
        }
    }

    if (node.rightchild != null) {
        if (node.rightchild.key > node.key)
            isBinarySearchTree(node.rightchild);
        else {
            System.out.println("false: " + node + " -> " + node.rightchild);
            return false;
        }
    }

    return true;
}

显然我要返回的方式有问题。如果所有 boolean 返回值都在逻辑 && 链中，这将起作用。只有当所有返回值都为真时，返回值才应该为 true。

我如何重写函数才能像那样工作？或者有可能吗？

Answer 1

我想这应该可行:

public static boolean isBinarySearchTree(Node node, int key) {
    if (node.leftchild != null && node.leftchild.key < key || node.rightchild != null && node.rightchild.key > key) {
        return false;
    } else {
        return (node.leftchild != null ? isBinarySearchTree(node.leftchild, node.leftchild.key) : true) && (node.rightchild != null ? isBinarySearchTree(node.rightchild, node.rightchild.key) : true);
    }
}