为什么 isBinarySearchTree() 函数不正确

Question

我正在检查一棵树是否是二叉搜索树。我看到了已知的解决方案。在查找之前，我根据 post 顺序遍历提出了以下尝试。我用手追踪过，似乎有道理。但是，这是不正确的。谁能帮我理解为什么？

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

boolean checkBST(Node root) {

    // Empty tree
    if (root == null) {
        return true;
    }

    // Sub trees are BST
    boolean valid = checkBST(root.left) && checkBST(root.right);     

    // Greater than left
    if (root.left != null) {
        valid = valid && root.data > root.left.data;
    }

    // Less than right
    if (root.right != null) {
        valid = valid && root.data < root.right.data;
    }

    return valid;
}

Answer 1

对于这个基本测试用例，您的代码将失败，因为它return对于以下情况是正确的：

问题是您的代码仅将节点与其直接子节点进行比较，而不是将其与整个子树进行比较。对于以 3 为根的 子树，它 return 是正确的，并且因为 3 < 50，您的代码最终 return 为真，这是错误的。

为什么 isBinarySearchTree() 函数不正确

Why isBinarySearchTree() function is not correct

java

algorithm

tree

recursion

binary-tree