如何验证给定树是否是二进制搜索树

Question

我想知道给定的二叉树是否是二叉搜索树.

我不知道该怎么办？

我唯一知道的是BST的inorder遍历将为您提供升序输出.

那么,这是我们需要验证的唯一条件,还是我们要检查的其他内容.

如果还有其他一些必要条件要检查,它们是什么？为什么需要检查这些条件？因为,我认为,如果给定的树是BST,INORDER遍历本身可以很容易地告诉你.

Answer 1

是的,如果对树的顺序遍历为您提供了一个严格单调的值列表,足以确定该树是BST.

Answer 2

根据二叉搜索树的定义，如果二叉树的每个节点都满足以下条件，那么它就是一棵二叉搜索树：

• 节点的左子树应该只包含键小于节点键的节点
• 节点的右子树应该只包含键大于节点键的节点
• 左右子树也必须是二叉搜索树。

如果中序遍历是升序，则上述所有条件都得到验证。