0

给定二叉搜索树(BST)。迭代地找到二叉搜索树的最大深度。

我知道使用队列 [level order traversal] 的方法,但时间复杂度是 O(N),因为我们需要访问整个树。但它不使用树是 BST 还是二叉树的信息。

BST 的算法是否保持不变,或者可以使用给定树是 BST 的事实来改进它?

4

1 回答 1

1

我不认为一棵树是 BST 或没有改变它的事实,在最坏的情况下你仍然必须访问所有节点,这使得它成为 O(N)。我猜在最好的情况下你只需要做 O(log(N)),但这是最好的情况,你只需沿着树的深度向下走,并且不访问其他节点。

于 2012-06-15T14:13:52.233 回答