二叉搜索树 (BST) 的中序遍历会产生排序序列。我想知道，如果我们对二叉树进行中序遍历并获得排序序列，是否意味着该树是 BST？ （这是充分必要条件吗？）
我正在寻找一种算法来检查给定的二叉树是否是具有最佳时间复杂度的 BST。解决方案之一here建议进行中序遍历并验证序列是否已排序。但我不明白为什么这是一个充分必要条件。我需要一个清晰且严格的证明。
我感谢任何帮助！
二叉搜索树（BST）的中序遍历确实会产生排序序列。然而，需要注意的是，虽然通过中序遍历获得的排序序列是树成为 BST 的必要条件，但它不是充分条件。
必要条件： 如果对二叉树进行中序遍历产生有序序列，则说明该树具有二叉搜索树性质。在 BST 中，对于任何给定的节点，其左子树中的所有节点的值都小于该节点，而其右子树中的所有节点的值都大于该节点。因此，以中序方式遍历树将按升序访问节点。
条件不足： 然而，反之则不一定成立。二叉树可以在有序遍历期间产生排序序列，但不是 BST。如果树具有与排序顺序对齐的结构，即使它不严格遵守 BST 属性，也会发生这种情况。
示例： 考虑以下二叉树：
2
/
1 3
/
4 5
中序遍历这棵树会产生序列 [4, 1, 5, 2, 3]，该序列已排序。然而，这棵树不是 BST，因为根的左子树包含一个大于根 (2) 的节点 (1)。
校样草图： 为了严格证明这一点，可以使用反例方法。构造不是 BST 的二叉树，但在有序遍历期间产生排序序列。通过演示这些反例，您可以表明中序遍历的排序序列并不是树成为 BST 的充分条件。