检查二叉树是否也是二叉搜索树的问题 [英] Issue checking if binary tree is also binary search tree

问题描述

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

I'm trying to solve this problem but I'm having some troubles:

在二叉搜索树（BST）中：

In a binary search tree (BST):

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


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

鉴于根节点：

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

确定二叉树是否也是二叉搜索树

Determine if the binary tree is also a binary search tree

我有这个代码：

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

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

This is working in some cases, but it fails in cases like this one:

如您所见，节点（ 4）在节点（3）的左子树中，虽然4大于3，所以该方法应该返回 false 。不过，我的代码返回 true 。

As you see, node (4) is in the node (3)'s left subtree, although 4 is greater than 3, so the method should return false. My code returns true, though.

我如何控制这种情况？如何检查左/右子树中的所有值是否低于/大于根（不仅是直接子）？

How could I control that case? How can I check that all the values in the left/right subtree are lower/greater than the root (not only the direct child)?

推荐答案

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

Your definitions are correct (although you don't necessarily need to insist that all the keys are distinct), but your code doesn't implement all the conditions in your definitions. Specifically, you don't enforce the minimum and maximum values in each subtree.

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

Here is an efficient recursive solution that implements your definitions:

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 ，你就不必担心了。

Note that I didn't bother checking for overflow in n.data-1 and n.data+1, which you would have to do in real life. If you want to allow duplicate keys, just change these to n.data and you don't have to worry about it.

这篇关于检查二叉树是否也是二叉搜索树的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！