没有最大值的二进制搜索树验证

Question

我构建了一个算法来验证树是否是二进制搜索树。它适用于大多数情况，但对于一些应该验证false的特定情况，它正在验证true。

这是我的算法：

public bool IsBinarySearchTree(BinaryTreeNode root)
{
if (root == null) return true;
if (
(root.Left != null && root.Value.CompareTo(root.Left.Value) < 0) ||
(root.Right != null && root.Value.CompareTo(root.Right.Value) > 0) ||
((root.Left != null && root.Right != null) && root.Left.Value.CompareTo(root.Right.Value) > 0)
)
return false;

return IsBinarySearchTree(root.Left) && IsBinarySearchTree(root.Right);
}

我看到一些代码在这种递归方法中使用了最小值和最大值，但我在这里没有使用。有人能帮我理解为什么这个代码在某些情况下会失败吗？

这里有一个场景，它应该验证为false，但它正在验证为true：

[Test]
public void OnIsBinarySearchTree_ShouldReturnTrue()
{
// Arrange
TreesAndGraphs.BinaryTreeNode rootNode = new TreesAndGraphs.BinaryTreeNode(10);
rootNode.Left = new TreesAndGraphs.BinaryTreeNode(8);
rootNode.Right = new TreesAndGraphs.BinaryTreeNode(12);
rootNode.Left.Left = new TreesAndGraphs.BinaryTreeNode(6);
rootNode.Left.Right = new TreesAndGraphs.BinaryTreeNode(11);
rootNode.Right.Left = new TreesAndGraphs.BinaryTreeNode(11);
rootNode.Right.Right = new TreesAndGraphs.BinaryTreeNode(13);
var treesAndGraphs = new TreesAndGraphs();
// Act
bool isBST = treesAndGraphs.IsBinarySearchTree(rootNode);
// Assert
Assert.That(isBST, Is.True);
}

我使用C#和NUnit来执行这个测试。

提前谢谢！

Answer 1

您的代码正在检查节点的左边子节点的值是否大于节点本身，或者节点的右边子节点的值是否小于节点本身。如果对于任何节点都不为真，则可以得出二进制搜索树有效的结论。

但这还不足以验证二进制搜索树。即使所有节点都通过了上述测试，您仍然可以拥有一个无效的二进制搜索树。这是代码返回错误结果的树的可视化：

__10__
/      
8        12
/       /  
6   11  11    13

正如你所看到的，每个左边的孩子都比它的父母小，每个右边的孩子都大于它的父母，所以这看起来很好，但最左边的11个仍然违反了规则：

在二进制搜索树中，父节点的左侧子树中的所有节点的值都应小于或等于父节点。节点11违反了此规则，很明显您的代码没有检测到这一点。