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

小编典典

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

algorithm

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

在二叉搜索树（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。

我该如何控制这种情况？如何检查左/右子树中的所有值都比根（而不是直接子代）低/大？

阅读 300

2020-07-28

共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-1and中的溢出n.data+1，这在现实生活中是必须要做的。如果您想允许重复的密钥，只需将其更改为，n.data而不必担心。

2020-07-28