一道微策略校招笔试题

MicroStrategy的题目出得真心有水平，下面是其中一道。

判断一棵二叉树是否为二叉搜索树(binary search tree)，二叉搜索树满足下列条件：

1. 根节点的值(key)比它的左子树所有节点的值都要大，比它的右子树所有节点的值都要小；

2. 左子树和右子树也都是二叉搜索树；

3. 不存在重复节点。

显然二叉搜索树的中序遍历结果正好是递增序列。假设中序遍历前一个节点的值为prev，那么它的后继节点的值一定比prev大，否则可以直接判定为false。

一种实现方法如下列代码所示：

bool isSuccessorBigger(TreeNode* ptr, int& prev){if (ptr == NULL)return true;if (isSuccessorBigger(ptr->left, prev)) {if (ptr->key > prev) {prev = ptr->key;return isSuccessorBigger(ptr->right, prev);}else { // in-order node falsereturn false;}}else { // left sub-tree falsereturn false;}}bool isBinarySearchTree(TreeNode* root){int prev = INT_MIN;return isSuccessorBigger(root, prev);}