正在解决 GeeksForGeeks 上的 "Check for BST" 个问题，但总是得到错误的答案，但我似乎找不到问题所在。有人可以解释一下吗？

Question

试图解决 GeeksForGeeks 上的“检查 BST”问题，但我不断收到错误消息，但我认为我的代码没有问题。有人可以看看我的代码并解释一下吗？谢谢。

public class Solution
{
    //Function to check whether a Binary Tree is BST or not.
    static boolean answer = true;
    
    boolean isBST(Node root)
    {
        // code here.
        if(root==null) return false;
        
        traverseLeft(root.left,root.data);
        traverseRight(root.right,root.data);
        return answer;
    }
    
    void traverseLeft(Node root, int val){
        if(root == null) return;
        
        if(root.data >= val){
             answer = false;
             return;
        }
        
        traverseLeft(root.left,root.data);
        traverseRight(root.right,root.data);
    }
    
    void traverseRight(Node root, int val){
        if(root == null) return;
        
        if(root.data <= val){
             answer = false;
             return;
        }
        
        traverseLeft(root.left,root.data);
        traverseRight(root.right,root.data);
    }
}

Answer 1

您的尝试存在几个问题：

result 不应该是静态变量。作为一个静态变量，它的值将在不同的测试用例中存在，在第一个测试有运行后永远不会重置为 true，因此可能会给出假阴性。

相反，您应该让递归函数 return BST 在 特定子树 中是否有效。然后调用者应该为它的 children 捕获布尔结果并执行逻辑与以确定它自己的响应是什么：当且仅当 [=39= 的两个递归调用都为真时才为真] 并且其本身的值在可接受的范围内。在所有其他情况下，它应该 return false。这样你就不需要更全局的变量了。
将节点的值与其 parent 的值进行比较是不够的。例如，您的逻辑会认为以下树是有效的 BST，但它不是：
```
        6
       /
      1
       \
        10
```
虽然值 10 通过了您的代码的测试（至少为 1），但它也不应大于 6。因此正确的算法将通过两个递归调用的限制值：下限和上限。

正在解决 GeeksForGeeks 上的 "Check for BST" 个问题，但总是得到错误的答案，但我似乎找不到问题所在。有人可以解释一下吗？

Solving "Check for BST" question on GeeksForGeeks but keep getting wrong answers but I can't seem to find the issue. Can someone please explain?

algorithm

tree

binary-search-tree