所以我在这个网站上找到了这个 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
更大,那么它将是错误的。我知道我们正在按顺序遍历树并检查它是否按顺序排列。然而,让我感到困惑的是每一行实际上在做什么。
有人可以详细说明这个函数是怎么回事吗?谢谢
最佳答案
首先,如果我们发现矛盾,我们可以立即返回 false
- 将其视为短路。此时树的其余部分无关紧要。
这两个 isBST
调用是有序遍历递归的简单部分。
当我们按顺序进行时,值严格递增(无重复)。所以如果我们看到不匹配,我们可以返回 false,所以这是正确的条件:
root->data <= prev->data
我无法在评论中设置示例格式,所以我在此处留下了一个显示@JerryCoffin 的解决方案将在何处失败的示例:
3
/ \
2 5
/ \
1 4
关于c++ - BST isBST() 解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33483751/