ツリー2つのノードを交換するためのトラバーサル

Question

私はこの問題に直面して、正しい解決策を考え出すことができたかどうか疑問に思っていました。この問題は、バイナリツリーの2つのノードを値だけでなくノードによってスワップすることに関係します。つまり、左右の値を変更する必要があります。

だから我々は、上記の画像のようなバイナリツリー何かを持っていることを言うことができます。私が最初に思ったのは、ノードのインオーダートラバーサルを作成し、ツリーを平坦化して要素を交換し、スワップされたリストからツリーを再構築できるようにすることでした。だから、文字通りソリューションは、上記のツリーでは、これ

のようなものになり、inorderをトラバーサルはこの、

1,3,4,6,7,8,10,13,14のようなリストが生成されます。

今、私は8と13

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

を入れ替えるしかし、私は木を平坦化されているので、ここでの問題は、あります今私が再構築しようとすると、特定のノードが左のサブファイルであるか、ルートであるかなど、個々のノードの位置がわからないため、私はそうすることができません。だから、文字通り、ツリーは、スワップされたノードで最初と同じように再生成することはできません。

ここで問題になるのは、各ノードの位置情報を保持するトラバーサルアルゴリズムを変更して、要素をスワップして再構築するときに、スワップされるノードが同じバイナリツリーになるかどうかです。インオーダートラバーサル中に個々のノードの状態/位置を保存できますか？

PS。ポストオーダーを実行すると、最初と最後のノードのリストがスワップされることになりますが、スワップする必要がある2つのノードは、必ずしもルートと最も右の要素にある必要はありません。

Answer 1

あなたの質問にはあいまいさがほとんどありません。 BSTの例のツリー（BSTはバイナリツリーです）でも、最終的な答えはBSTプロパティを破ることができます。私はその答えが必要なものと推定しています。私が間違っているなら、私を訂正してください。

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

私は、トラバースと平坦化の観点から言えば、たった1回のトラバーサルでツリーを再構築することはできません。ツリーを構築するには、2つのトラバーサルが必要です。それは

以下
1. 事前注文と注文
2. でポスト順序のいずれかであると
ためには、レベル順とために

だからのいずれかにスワップを行います2つのトラバーサルとrecontruct。それは答えを与えるはずです。

タイムコンプがO（n）であるため、2番目のソリューションははるかに効率的なソリューションです。この方法では、ツリー全体を走査し、2つの候補ノードへの参照ポインタを得る。参照を取得したら、一時変数を使用して情報を交換します。この方法は複雑ですが、前のアプローチよりも時間と空間の両方が効率的です。

---

HWの質問ではない場合は、タグを付けてください！

例：

  4 
     2  6 
     1 3 5 7 

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

今、あなたが知っていますこのツリーのルートは4です（ルートはPreorderの最初の要素として出力されるため）。 4に基づいて、トラバースを分割します。

ここで、左のサブツリーは になります。Pre：2 1 3; Inorder：1 2 3

右サブツリーは Pre：6 5 7となります。 Inorder：5 6 7

これを再帰的にやり続けると、それは答えになります！