c++ - 是一个二叉树 BST 但只有右 child 才允许重复

Question

我正在尝试解决一个问题，看看二叉树是否是 BST。我找到的解决方案是针对没有重复项的二叉树。 Geeksforgeeks link

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 

/* Returns true if the given tree is a BST and its 
   values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max) 
{ 
  /* an empty tree is BST */
  if (node==NULL) 
     return 1;

  /* false if this node violates the min/max constraint */ 
  if (node->data < min || node->data > max) 
     return 0; 

  /* otherwise check the subtrees recursively, 
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, node->data-1) &&  // Allow only distinct values
    isBSTUtil(node->right, node->data+1, max);  // Allow only distinct values
} 

对于重复项，我只是更改了以下部分。同样只能在右子节点中找到重复项，即左子节点中的所有子节点都应该比当前节点小，但右子节点的值可能与父节点相同。

  if (node->data < min || node->data >= max) 
     return 0;
return(isBSTUtil(node->left, min, node->data) && 
isBSTUtil(node->right, node->data, max));

我不知道我哪里错了，但有些测试失败了。这是一个在线评估，我无法获得失败的测试用例。有人可以帮我解决这个问题吗？

Answer 1

试试下面的代码:

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 

/* Returns true if the given tree is a BST and its 
   values are >= min and <= max. */
int isBSTUtil(struct node* node, long long min, long long max) 
{ 
  /* an empty tree is BST */
  if (node==NULL) 
     return 1;

  /* false if this node violates the min/max constraint */ 
  if (node->data < min || node->data > max) 
     return 0; 

  /* otherwise check the subtrees recursively, 
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, long long (node->data) - 1) &&  /*left smaller*/
    isBSTUtil(node->right, node->data, max);  /*right can equal or greater*/
} 

为避免下溢，您应该使用 long long 而不是 int。 long 在某些平台上也是 4 字节，但还不够。 感谢@Bernard指出。