0

与えられた二分探索木 (BST)。二分探索木の最大深さを繰り返し求めます。

キュー [レベル順トラバーサル] を使用する方法は知っていますが、ツリー全体にアクセスする必要があるため、時間の複雑さは O(N) です。ただし、ツリーが BST ツリーかバイナリ ツリーかの情報は使用しません。

BST のアルゴリズムは同じままですか、それとも、指定されたツリーが BST であるという事実を使用して改善できますか?

4

1 に答える 1

1

ツリーがBSTである、またはツリーに何も変更されないという事実はないと思います。最悪の場合でも、すべてのノードにアクセスする必要があり、O（N）になります。最良の場合は、O（log（N））を実行するだけでよいと思いますが、それは、ツリーの深さを下って他のノードにアクセスしないという、可能な限り最良の場合です。

于 2012-06-15T14:13:52.233 に答える