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

Question

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

In a binary search tree (BST):

• The data value of every node in a node's left subtree is less than the data value of that node.
• The data value of every node in a node's right subtree is greater than the data value of that node.

Given the root node:

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

这在某些情况下有效，但在这种情况下会失败:

如您所见，节点(4) 位于节点(3) 的左子树中，尽管4 大于3，因此该方法应返回假。不过，我的代码返回 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，你不必担心它。