今天我参加了一场面试，被要求编写一个程序，该程序接收一棵二叉树并返回 true（如果它也是二叉搜索树）否则返回 false。
我的解决方法1：执行中序遍历并在 O(n) 时间内存储元素。现在扫描元素的数组/列表，并检查第i个元素是否大于(i+1)个元素。如果遇到这种情况，请返回false并跳出循环。(这需要O(n)时间)。最后返回true。
但这位绅士希望我提供一个高效的解决方案。我尝试了但是不成功，因为要找出它是否是BST，我必须检查每个节点。
此外他建议我考虑使用递归。
我的解决方法2：如果对于任何节点N N->left < N且N->right > N，则BT是BST，以及N的左节点的中序继承者小于N，N的右节点的中序继承者大于N，左子树和右子树都是BST。
但这将变得复杂且运行时间似乎不好。如果你知道任何最优解，请帮忙。
这是一个比较常见的问题，有以下回答：
public boolean isValid(Node root) {
return isValidBST(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
if(node == null)
return true;
return node.value > l
&& node.value < h
&& isValidBST(node.left, l, node.value)
&& isValidBST(node.right, node.value, h);
}
递归调用确保子树节点在其祖先的范围内，这很重要。由于每个节点只被检查一次，因此运行时间复杂度将为O(n)。
另一个解决方案是进行中序遍历并检查序列是否已排序，特别是因为您已知输入是二叉树。
@Dhruv提供的答案是很好的。除此之外，这里还有一种在O(n)时间内有效的解决方案。
我们需要在这种方法中跟踪上一个节点。在每个递归调用中，我们检查上一个节点数据与当前节点数据是否相同。如果当前节点数据小于上一个，则返回false。
int isBST(node* root) {
static node* prev = NULL;
if(root==NULL)
return 1;
if(!isBST(root->left))
return 0;
if(prev!=NULL && root->data<=prev->data)
return 0;
prev = root;
return isBST(root->right);
}
prev!=NULL && root->data<=prev->data ...不正确...如果第二个左子节点大于父节点，这个算法将会失败！ - NoobEditor[10 8 15 5 12]。 - NoobEditorboolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max){
if(node == null){
return true;
}
boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);
return left && right && (node.getValue()<max) && (node.getValue()>=min);
}
欢迎留言评论。谢谢。
我认为第二种方法是正确的。可以以递归方式遍历树。在每次迭代中，可以存储当前子树的下限和上限。如果我们想要检查以x为根的子树，并且子树的边界为l和h，则我们只需要检查l <= x <= h并检查具有边界l和x的左子树以及具有边界x和h的右子树。
这将具有O(n)的复杂度，因为我们从根开始，每个节点仅作为某个子树的根节点被检查一次。此外，我们需要O(h)的内存用于递归调用，其中h是树的高度。
上面有一些使用INTEGER.MAX和MIN的示例，我看不出通过它们的原因和意义， 如果我有任何错误，请纠正我或解释一下原因。
此外，二叉搜索树可能具有通过compareTo方法或Coperator进行比较的对象..（因此Integer.MIN和Integer.MAX不适用于该模型） 我正在编写一个代码，它返回true或false 必须调用（root_node，true），如果它是bst，则它将返回true，否则返回false
void boolean isBSt( node root_node, boolean passed_root)
{
if ( node==null){
if ( passed_root)
return false;
// you have passed null pointer as
//root of the tree , since there is no
// valid start point we can throw an exception or return false
return true;
}
if( node.right !=null )
if ( node.right.data <= node.data)
return false;
if ( node.left !=null )
if ! ( node.left.data <= node.data)
return false;
return ( isBST( node.right , false) && isBST( node.left, false ) )
}
这里有另一种解决方案，它使用2个辅助函数来计算每个节点子树中的最小值和最大值，使用辅助函数minValue和maxValue。
int isBST(struct node* node)
{
if (node == NULL)
return(true);
/* false if the max of the left is > than us */
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);
}