0

この問題に遭遇したばかりで、正しい解決策を思いつくことができるかどうか疑問に思っていました. この問題は、バイナリ ツリーの 2 つのノードを値だけでなくノードごとに交換することに関係しています。つまり、左右の値も変更する必要があります。

BST

上の画像のような二分木があるとしましょう。私が最初に考えたのは、ツリーを平坦化し、要素を交換して、交換されたリストからツリーを再構築できるように、ノードの順序通りのトラバーサルを行うことでした。文字通り、解決策は次のようになります

上記のツリーの場合、インオーダー トラバーサルは次のようなリストを生成します。

1,3,4,6,7,8,10,13,14.

今度は 8 と 13 を交換します。

=> 1,3,4,6,7,13,10,8,14

しかし、ここでの問題は、特定のノードが左のサブチャイルドであるかどうか、またはそれがルート。したがって、文字通り、スワップされたノードを使用した最初と同じようにツリーを再生成することはできません。

問題は、各ノードの位置情報を保持するようにトラバーサル アルゴリズムを変更して、要素を交換して再構築するときに、目的のノードが交換された同じバイナリ ツリーを作成できるかどうかです。順序通りのトラバーサル中に個々のノードの状態/位置を保存できますか?

PS。ポストオーダーを行うと、最初と最後のノードがスワップされるリストが作成されることを認識していますが、スワップする必要がある 2 つのノードは、必ずしもルートと右端の要素にある必要はなく、任意の 2 つにすることができます。

4

1 に答える 1

0

あなたの質問にはあいまいさがほとんどありません。BST の例のツリー (ただし、BST はバイナリ ツリーでもあります) と最終的な答えは、BST プロパティを壊す可能性があります。それが答えである必要があると思います。私が間違っている場合は修正してください。

答えに関する限り、2つの解決策があります。

トラバーサルとフラット化の観点から言えば、たった 1 回のトラバーサルでツリーを再構築することはできません。ツリーを構築するには 2 回のトラバーサルが必要です。以下のいずれかになります

  1. 予約注文と注文中
  2. ポストオーダーとインオーダー
  3. レベル順とイン順

したがって、2 つのトラバーサルのいずれかでスワッピングを行い、再構築します。それは答えを与えるはずです。

2 番目のソリューションは、Time Comp が O(n) であるため、はるかに優れた効率的なソリューションです。このメソッドでは、ツリー全体をトラバーサルし、2 つの候補ノードへの参照ポインターを取得します。参照を取得したら、一時変数を使用して情報を交換します。この方法は複雑ですが、前の方法よりもスペースと時間の両方が効率的です。

ハードウェアに関する質問ではないことを願っています。もしそうなら、タグ付けしてください!

例:

            4
        2       6
      1   3   5   7

このツリーの順序トラバーサルは次のようになります。 Pre : 4 2 1 3 6 5 7 Inorder : 1 2 3 4 5 6 7

これで、4 がこのツリーのルートであることがわかりました (ルートは Preorder の最初の要素として出力されるため)。4 に基づいて、トラバーサルを分割します。

左のサブツリーは Pre : 2 1 3 ; になります。順番 : 1 2 3

右側のサブツリーは Pre : 6 5 7 になります。順番 : 5 6 7

これを再帰的に続けてください。それが答えです。

于 2011-10-28T03:05:42.750 に答える