如何检查给定的BST是否有效？[重复]

Question

我试图检查一个给定的二叉树是否是二叉查找树。我要做的是对二叉树进行有序遍历，并将当前元素与前一个元素进行比较。如果当前元素更大，我们继续进一步检查，否则给定的树是无效的。

int prev=0;
public int isValidBST(TreeNode A) {
    if(A==null)
    return 1;
    isValidBST(A.left);
  //  System.out.println("val "+A.val);
   if(A.val<=prev)
   return 0;
   // else if(A!=null){
    prev=A.val;

    //System.out.println("prev "+prev);
    isValidBST(A.right);
    if(isValidBST(A.right)==1&&isValidBST(A.left)==1)
    return 1;
    return 0;
}

这是我写的代码。我到底做错了什么？

Answer 1

> < li >建议:您可以让您的方法返回boolean而不是int。 < li >此外，我更喜欢使用空节点而不是变量。通过这种方式，你可以让你的树存储除整数以外的值(只需要改变比较逻辑)。 < li>

如果您希望树也具有非唯一值，则可以从< code>node.data中删除等号

TreeNode prev=null;
public boolean isValidBST(TreeNode node)
{
    //null is a valid bst
    if(node==null){
        return true;
    }

    // traverse the tree in inorder fashion and
    // keep a track of previous node
    if (!isValidBST(node.left)){
        return false;
      }

    // compare current data with previous one
   if (prev != null && node.data <= prev.data){
       return false;
   }

   prev = node;

   //check right subtree
   return isValidBST(node.right);
}

Answer 2

每个子树只有一个递归调用！使用布尔值！

int prev=0;
public boolean isValidBST(TreeNode A) {
    if( A == null ) return true;
    if( ! isValidBST(A.left) ) return false;
    if( A.val <= prev ) return false;
    prev = A.val;
    if( ! isValidBST(A.right) ) return false;
    return true;
}