验证二叉搜索树的正确性：算法挑战与C++解决方案

这篇文章将探讨如何验证一个给定的二叉树结构是否为正确的二叉搜索树。我们将深入浅出地解释问题，并提供使用C++实现的解决方案。

问题描述

给定一个以整数作为键值的二叉树，你需要验证它是否是一个正确的二叉搜索树。二叉搜索树的定义如下：对于树中的任意节点，如果其键值为 x，则其左子树中所有节点的键值必须严格小于 x，而其右子树中所有节点的键值必须严格大于 x。换句话说，较小的元素位于左侧，较大的元素位于右侧。你需要检查给定的二叉树结构是否满足此条件。你可以假设输入是一个有效的二叉树，即它是一棵树，并且每个节点最多有两个子节点。

输入格式

第一行包含顶点数 n。树的顶点编号从 0 到 n - 1，其中顶点 0 是根节点。

接下来的 n 行包含有关顶点 0, 1, ..., n-1 的信息。每行包含三个整数 key_i, left_i 和 right_i，分别表示第 i 个顶点的键值、左子节点的索引和右子节点的索引。如果第 i 个顶点没有左子节点或右子节点（或都没有），则相应的 left_i 或 right_i（或两者）将等于 -1。

约束条件

0 ≤ n ≤ 10^5* -2^31 < key_i < 2^31 - 1* -1 ≤ left_i, right_i ≤ n - 1

保证输入表示一个有效的二叉树。特别地，如果 left_i ≠ -1 且 right_i ≠ -1，则 left_i ≠ right_i。此外，一个顶点不能是两个不同顶点的子节点。并且，每个顶点都是根节点的后代。输入中的所有键值都将不同。

输出格式

如果给定的二叉树是正确的二叉搜索树（参见问题描述中的定义），则输出一个单词 'CORRECT'（不带引号）。否则，输出一个单词 'INCORRECT'（不带引号）。

C++ 解决方案

下面是一个使用C++语言解决这个问题的示例代码：cpp#include #include #include

using namespace std;

struct Node { int key; int left; int right;};

bool isBSTUtil(vector& tree, int index, int minValue, int maxValue) { if (index == -1) { return true; } if (tree[index].key < minValue || tree[index].key > maxValue) { return false; } return isBSTUtil(tree, tree[index].left, minValue, tree[index].key - 1) && isBSTUtil(tree, tree[index].right, tree[index].key + 1, maxValue);}

bool isBinarySearchTree(vector& tree) { int minValue = numeric_limits::min(); int maxValue = numeric_limits::max(); return isBSTUtil(tree, 0, minValue, maxValue);}

int main() { int n; cin >> n; vector tree(n); for (int i = 0; i < n; i++) { cin >> tree[i].key >> tree[i].left >> tree[i].right; } if (isBinarySearchTree(tree)) { cout << 'CORRECT' << endl; } else { cout << 'INCORRECT' << endl; } return 0;}

代码解释

代码使用递归函数 isBSTUtil 来检查二叉树是否为二叉搜索树。该函数接受树、当前节点索引、最小允许值和最大允许值作为参数。它检查当前节点的值是否在允许的范围内，然后递归地调用自身来检查左子树和右子树。

测试用例

你可以将上述代码复制并粘贴到一个C++编译器中进行测试。输入格式可以按照题目描述进行输入，然后你将获得一个输出结果，表示给定的二叉树是否是一个正确的二叉搜索树。如果是正确的二叉搜索树，则输出'CORRECT'；如果不是，则输出'INCORRECT'。