今天我接受采访时,我被要求编写一个程序,该程序采用二叉树,如果它也是二进制搜索树则返回true,否则为false.
我的方法1:执行有序遍历并将元素存储在O(n)时间内.现在扫描数组/元素列表并检查第 i 个索引处的元素是否大于第(i + 1)个索引处的元素.如果遇到这种情况,则返回false并退出循环.(这需要O(n)时间).最后回归真实.
但这位先生希望我提供一个有效的解决方案.我尝试但是我没有成功,因为要查找它是否是BST我必须检查每个节点.
而且他指着我思考递归.我的方法2:如果对于任何节点N N>左<N和N>右> N,并且N的左节点的有序后继小于N并且有序后继,则BT是BST N的右节点大于N,左右子树是BST.
但这会很复杂,而且运行时间似乎并不好.如果您知道任何最佳解决方案,请帮忙.