i**9
发帖数: 351 | 1 很多人给出的答案
int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the max of the left is > than us
// (bug -- an earlier version had min/max backwards here)
if (node->left!=NULL && maxValue(node->left) > node->data)
return(false);
// false if the min of the right is <= than us
if (node->right!=NULL && minValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);
// passing all that, it's a BST
return(true);
}
我怎么觉得在第三次判断的时候应该是（只有小于号，没有等于号）
// false if the min of the right is < than us
if (node->right!=NULL && minValue(node->right) < node->data)
return(false);
右子树值等于root值也有应该是valid binary search tree, 大家讨论讨论？ |
l*****a
发帖数: 14598 | 2 Binary search tree
From Wikipedia, the free encyclopedia
In computer science, a binary search tree (BST) or ordered binary tree
is a node-based binary tree data structure which has the following
properties:
The left subtree of a node contains only nodes with keys less than the
node's key.
The right subtree of a node contains only nodes with keys greater than
the node's key.
Both the left and right subtrees must also be binary search trees.
【在 i**9 的大作中提到】
: 很多人给出的答案
: int isBST(struct node* node) {
: if (node==NULL) return(true);
: // false if the max of the left is > than us
: // (bug -- an earlier version had min/max backwards here)
: if (node->left!=NULL && maxValue(node->left) > node->data)
: return(false);
: // false if the min of the right is <= than us
: if (node->right!=NULL && minValue(node->right) <= node->data)
: return(false);
|
z****n
发帖数: 1379 | 3 很多人给出的答案不是这个吧
这个复杂度太高了，很多重复计算
正解是传当前最小最大值给递归函数
至于小于还是小于等于号，不是那么重要，可以临时跟面试官商讨定义
【在 i**9 的大作中提到】
: 很多人给出的答案
: int isBST(struct node* node) {
: if (node==NULL) return(true);
: // false if the max of the left is > than us
: // (bug -- an earlier version had min/max backwards here)
: if (node->left!=NULL && maxValue(node->left) > node->data)
: return(false);
: // false if the min of the right is <= than us
: if (node->right!=NULL && minValue(node->right) <= node->data)
: return(false);
|
d**e
发帖数: 6098 | 4 最简单的应该是inorder，如果递增就是bst
【在 z****n 的大作中提到】
: 很多人给出的答案不是这个吧
: 这个复杂度太高了，很多重复计算
: 正解是传当前最小最大值给递归函数
: 至于小于还是小于等于号，不是那么重要，可以临时跟面试官商讨定义
|
z****n
发帖数: 1379 | 5 复杂度一样的吧，还多申请了一个变量储存上一个值：）
【在 d**e 的大作中提到】
: 最简单的应该是inorder，如果递增就是bst
|
p********7
发帖数: 549 | 6 如果是等于就不是BST了
【在 z****n 的大作中提到】
: 很多人给出的答案不是这个吧
: 这个复杂度太高了，很多重复计算
: 正解是传当前最小最大值给递归函数
: 至于小于还是小于等于号，不是那么重要，可以临时跟面试官商讨定义
|
c***2
发帖数: 838 | 7 Here's my version:
boolean is_binary_search_tree (tree_node_type *root)
{
if ((!root)||(!root->left && !root->right))
return TRUE;
if(root->left){
if(root->right) {
if(TREE_GT>tree_compare(root->left,root,NULL)&&
TREE_GT>tree_compare(root,root->right,NULL))
return is_binary_search_tree(root->left)&&is_binary_search_
tree(root->right);
else
return FALSE;
}
else
return is_binary_search_tree(root->left);
}
else
return is_binary_search_tree(root->right);
} |
