1

にある特定の範囲内のすべての整数を見つけることに興味がありBSTます。BSTがノードで作成されている場合、これをどのように行うのでしょうか。したがって、単一リンクリストを使用する必要があります。返されるリンク リスト内のアイテムの順序は重要ではありません。

たとえば、以下に示すツリーを考えてみましょう。

ここに画像の説明を入力

範囲は [6, 13] で、リストには 6->7->8->10->13 または 13->10->8->7->6 が含まれている必要があります。私が言ったように、返されるリストでは順序は重要ではありません。

また、実行時の制約は O(n) です。ここで、n はツリー内のノードの数です。

前もって感謝します！

4

2 に答える 2

1

BST の基本的な知識があれば、ツリーから並べ替えられた要素のセットを取得することは、実際には非常に簡単であることに精通しているはずです。LVR/ traversingに精通している場合はRVL、「答え」にスキップできます。

ツリーを繰り返しトラバースする:

ツリーのトラバースは、通常、3 文字の組み合わせで表されLVRます。L残っています。Rは正しい。V訪問を意味します。

これは、ツリーをトラバースするときにたどるパターンを示しています。Lツリーが存在する場合は、ツリーを左のノードまで上っていくという意味です。R正しい。V現在のノードでの印刷などの操作を意味します。再帰を使用します。それは非常に重要です。

今。ソートされたセットを取得する方法。LVR訪問が印刷またはプッシュを意味する場合は簡単です。

例 - 完全なウォークスルー:

 (8) You start in root. `L` - go left. 
  (3) You are in (3). You go `LVR` for this node again - recurrence. `L`
    (1) You are in (1). Now *again* `LVR`.
    However there is no left node so we go to `V` - visit/print 1. Now `R` - no right node. End. By recurrence we go back to 3.
  (3) - We're done with `L`. We do `V`. Print 3.
  (3) - `R`.
    (6) You are in (6) - `LVR` again. 'L'
      (4) You are in (4) - `L` does not exists. Print 4. `R` does not exist. Back one level.
    (6) - `V`. Print 6.
    (6) - `R`.
      You are in (7) - `L` does not exists. Print 7. `R` does not exist. Back one level.
    (6) - `LVR` Done. Back one level.
  (3) - `LVR` Done. Back one level.
(8) - `R`.
  (10) You are in 10. `L` Does not exist.
  (10) `V`. Print 10.
  (10) `R`.
    (14) You are in 14.
    (14) `L`.
      (13) You are in 13. `L` does not exists. Print 14. `R` does not exist. Back one level.
    (14) `V`. Print 14.
    (14) `R`. Does not exist. Back one level.
  (10) Done with `R`. Back one level.
(8) Done with `R`. Back one level.
Haha we were on root node so we are done.

プリントをフォローする場合。セット全体を最低から最高の順に印刷したことがわかります。RVLpattern も同様ですが、最初に右に行くため、最初に最も右側のノードにアクセスするため、順序は降順になります。魔法はなく、各ノードに 1 回だけアクセスするため、時間計算量はO(n)です。

答え：

簡単な方法。通常のLVRトラバースを行います。ただし、範囲に収まる場合にのみ数値を出力します。少し難しいですが、平均的および極端なケースの方が優れています。開始ノードを見つけます。次に、トラバースを開始し、各訪問で上限とのみ比較し、ノード データがそれを超えると停止します。

もちろん、印刷する代わりに、要素を並べ替えた順序で保存するために、スタックまたは他のもの (リストなど) を使用できます。

于 2013-04-16T09:24:58.157 に答える