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

Question

我正试图解决这个问题,但我遇到了一些麻烦:

在二叉搜索树(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;
}

这在某些情况下有效,但在以下情况下失败:

如您所见,node (4)位于node (3)的左子树中,尽管4大于3,因此该方法应该返回false.但是,我的代码返回了true.

我怎么能控制那个案子？如何检查左/右子树中的所有值是否低于/大于根(不仅是直接子)？

Answer 1

您的定义是正确的(尽管您不一定要坚持所有密钥都是不同的),但您的代码并未实现定义中的所有条件.具体而言,您不会在每个子树中强制执行最小值和最大值.

这是一个有效的递归解决方案,可以实现您的定义:

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和n.data+1,你将不得不在现实生活中做.如果您想允许重复的密钥,只需将这些密钥更改为n.data,您就不必担心它.