检查二叉树是否也是二叉搜索树的问题

我正在尝试解决这个问题，但遇到了一些麻烦：

在二叉搜索树 (BST) 中：

• 某个节点的左子树中每个节点的数据值都小于该节点的数据值。
• 节点右子树中每个节点的数据值都大于该节点的数据值。

给定根节点：

class Node {
    int data;
    Node left;
    Node right;
}

判断二叉树是否也是二叉搜索树

我有这个代码：

boolean check(Node root) {   

    //node doesn't have any children
    if (root.left == null && root.right == null) {
        return true;
    }

    boolean leftIsBst = true;
    boolean rightIsBst = true;

    if (root.left != null) {
        leftIsBst = (root.left.data < root.data) && check(root.left);
    }

    if (root.right != null) {
        rightIsBst = (root.right.data > root.data) && check(root.right);
    }

    return leftIsBst && rightIsBst;
}

这在某些情况下有效，但在以下情况下会失败：

如您所见，节点(4)位于节点中(3)的左子树，虽然 4 大于 3，所以该方法应该返回false。我的代码返回true， 尽管。

我怎样才能控制这个案子？如何检查左/右子树中的所有值是否低于/大于根（不仅仅是直接子树）？

您的定义是正确的（尽管您不一定需要坚持所有键都是不同的），但您的代码并未实现定义中的所有条件。具体来说，您不会强制每个子树中的最小值和最大值。

这是一个实现您的定义的有效递归解决方案：

boolean check(Node root) {
    return check(root, INT_MIN, INT_MAX);
}
boolean check(Node n, int minval, int maxval) {
    if (n == null) {
        return true;
    }
    return (
        n.data >= minval && n.data <= maxval &&
        check(n.left, minval, n.data-1) &&
        check(n.right, n.data+1, maxval)
    );
}

请注意，我没有费心检查溢出n.data-1 and n.data+1，这是你在现实生活中必须做的。如果你想允许重复的键，只需将它们更改为n.data你不必担心它。