验证二叉树是否为 BST 的最佳算法如下
IsValidBST(root,-infinity,infinity);
bool IsValidBST(BinaryNode node, int MIN, int MAX)
{
if(node == null)
return true;
if(node.element > MIN
&& node.element < MAX
&& IsValidBST(node.left,MIN,node.element)
&& IsValidBST(node.right,node.element,MAX))
return true;
else
return false;
}
这个逻辑的空间复杂度显然是O(logN)我假设这是递归的成本。价值是如何得出的？
我的评论升级为回答：
除了方法变量和返回值之外，没有使用任何其他数据，因此实际上，所有内存都是“递归成本”。因此，总成本与树的深度成线性比例。
In a 平衡二叉搜索树，深度为O(log n)，所以实际上，空间复杂度是O(log n)也。然而，一般来说，BST不一定是平衡的，它甚至可以是长度为n的链，如果根是最小的，那么它的右孩子是第二小的元素，依此类推。在这种情况下，该递归的空间复杂度为O(n).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
