c++ - BST isBST() 解释

Question

所以我在这个网站上找到了这个 isBST() 函数:

static struct node *prev = NULL;

bool isBST(struct node* root)
{
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }

    return true;
}

我在跟踪发生的事情时遇到了一些麻烦。主要是

 if (!isBST(root->left))
          return false;

和

if (prev != NULL && root->data <= prev->data)
              return false;

if (prev != NULL && root->data <= prev->data)出于某种原因对我来说似乎倒退了。我认为应该是 if (prev != NULL && root->data >= prev->data)因为如果 root->data更大，那么它将是错误的。我知道我们正在按顺序遍历树并检查它是否按顺序排列。然而，让我感到困惑的是每一行实际上在做什么。

有人可以详细说明这个函数是怎么回事吗？谢谢

Answer 1

首先，如果我们发现矛盾，我们可以立即返回 false - 将其视为短路。此时树的其余部分无关紧要。

这两个 isBST 调用是有序遍历递归的简单部分。

当我们按顺序进行时，值严格递增(无重复)。所以如果我们看到不匹配，我们可以返回 false，所以这是正确的条件:

root->data <= prev->data

---

我无法在评论中设置示例格式，所以我在此处留下了一个显示@JerryCoffin 的解决方案将在何处失败的示例:

    3
   / \ 
  2   5
 / \
1   4