布尔递归的替代方法

Question

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

这是函数开始的地方：

isBinarySearchTree(root)

函数：

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;
}

显然我想要的方式有问题return。如果所有布尔 return 值都在逻辑 && 链中，这将起作用。如果所有 return 值都为真，则 return 值只能为 true。

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

Answer 1

您需要对左边的测试结果和右边的测试结果进行逻辑与运算，然后 return 结果，例如 return (leftnode == null || (leftnode.key < key && isBinarySearchTree(leftnode))) && (rightnode == null || (key < rightnode.key && isBinarySearchTree(rightnode)));。不过，将其分成几行可能会更清楚。

Answer 2

我想这应该可行：

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);
    }
}

Answer 3

        public static boolean isBinarySearchTree(Node node) {

         if(node==null)
            return false;
         if(node.left!=null &&node.key <node.left||node.right!=null &&node.key >node.right)
        return false;
    if((getMax(node.left)>getMin(node.right)) //Left subtree should not have a value which larger than min in right subtree
     return false;
//check recurisvely left and right subtrees
     if(!(isBinarySearchTree(node.left)&&isBinarySearchTree(node.right)))
     return false;

     return true;