判断一个树是不是BST
因为BST是对于每一个点,左子树的所有节点都小于当前点,右子树的所有节点都大于当前点。所以其实每个子树代表一段值,可以用当前点是否超出了[min, max]范围判断是否是二叉树。
bool isBST(TreeNode* root, int min, int max) {
if (root == NULL) return 1;
if (root->val < min || root->val > max) return 0;
return isBST(root->left, min, node->val - 1) &&
isBST(root->right, node->val + 1, max);
}
return isBST(root, INT_MIN, INT_MAX);