2014-05-02 07:18
原题：
boolean isBST(const Node* node) {
// return true iff the tree with root 'node' is a binary search tree.
// 'node' is guaranteed to be a binary tree.
}
n
/ \
a b
\
c
题目：检查一棵二叉树是否为二叉搜索树。
解法：二叉搜索树，就是每个节点的左边全都小于它，右边全都大于它。如果真的对于每个节点都全部检查左右边的每个节点，就做了很多重复劳动。只需要判断每个节点的左子树最靠右，和右子树最靠左的节点是否小于和大于它即可。递归过程中传递引用可以随时更新两个需要检查的值。请看代码。
代码：
// http://www.careercup.com/question?id=5632735657852928
#include <climits>
#include <iostream>
#include <sstream>
#include <string>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int _val = ): val(_val), left(nullptr),right(nullptr) {};
}; class Solution {
public:
bool isBST(TreeNode *root) {
if (root == nullptr) {
return false;
} max_val = INT_MIN;
res = true;
first_node = true;
isBSTRecursive(root); return res;
};
private:
int max_val;
bool res;
bool first_node; void isBSTRecursive(TreeNode *root) {
if (!res) {
return;
} // root is guaranteed to be not nullptr.
if (root->left) {
isBSTRecursive(root->left);
}
if (first_node || root->val > max_val) {
first_node = false;
max_val = root->val;
} else {
res = false;
return;
}
if (root->right) {
isBSTRecursive(root->right);
}
};
}; void construcTree(TreeNode *&root)
{
int val;
stringstream sio;
string s; if (cin >> s && s != "#") {
sio << s;
sio >> val;
root = new TreeNode(val);
construcTree(root->left);
construcTree(root->right);
} else {
root = nullptr;
}
} void deleteTree(TreeNode *&root)
{
if (root == nullptr) {
return;
}
deleteTree(root->left);
deleteTree(root->right);
delete root;
root = nullptr;
} int main()
{
TreeNode *root;
Solution sol; while (true) {
construcTree(root);
if (root == nullptr) {
break;
} cout << (sol.isBST(root) ? "Valid BST" : "Invalid BST") << endl; deleteTree(root);
} return ;
}