如何检查一个二叉树是否为二叉搜索树

原理

搜索二叉树有2个基本性质可以用于判断：

1. 左子树中的所有值都小于等于根节点的值，而右子树中的数据都大于根节点的值。
2. 二叉搜索树的中序输出后数据按照非递减顺序排列

对于第一个性质，假设根节点数据为7，那么左子树最大不能超过7，而右子树都大于7。

所以我们可以在函数中增加参数minValue和maxValue，用来记录此子树中数据的范围。

代码I

bool IsBST(BstNode* root, int minValue, int maxValue) {
	if (root == NULL)return true;
	if (root->data >= minValue && root->data < maxValue
		&& IsBST(root->left, minValue, root->data) && IsBST(root->right, root->data, maxValue))
		return true;
	else
		return false;
}
bool IsBinarySearchTree(BstNode* root) {
	return IsBST(root, INT_MIN, INT_MAX);
}

代码II

void LDR(BstNode* root, vector<int>& A) {
	if (root == NULL)return;
	LDR(root->left,A);
	A.push_back(root->data);
	LDR(root->right,A);
}
bool ISBST(BstNode* root) {
	vector<int> A;
	LDR(root,A);
	for (int i = 0; i < A.size() - 1; i++) {
		if (A[i] >A[i + 1])return false;
	}
	return true;
}