問題の説明:
R. ボリスト教授は樹木を研究しています。彼は、お気に入りのすべてのツリーの事前順、順序順、および後順トラバーサルの記録を保持しています。しかし、彼のオフィスでの火災により、彼が順番通りのトラバーサルを保管していたファイル キャビネットが破壊されました。彼はお気に入りの木すべての前順と後順のトラバーサルをまだ持っていますが、これは欠落しているインオーダーのトラバーサルを再構築するのに十分な情報ですか?
次のタスクのプログラムを設計して実装する必要があります。入力は 2 つの数値リストで構成されます。最初のリストは、あるツリー T の前順トラバーサルです。2 番目のリストは、同じツリー T の後順トラバーサルです。出力は、T のインオーダー トラバーサルでなければなりません。入力が一意のツリーを決定しない場合、任意の一貫したインオーダー トラバーサル返品できます。
実装の設計に役立つ場合は、次のことを想定できます。
- 1,000 を超えるノードを持つツリーはありません。
- 複数のノードに同じラベルを使用するツリーはありません。
- ノードのラベルは 0 から 10,000 までの数字です。
サンプルデータ
Input:
2 6 7 1 11 8 5 10 3 4 9
7 8 5 11 10 1 6 4 9 3 2
Output:
7 6 8 11 5 1 10 2 4 3 9
ヒント
ツリーの前順および後順トラバーサルが与えられた場合、どの要素がルートであったかを推測できますか? 左のサブツリーから派生した要素はどれですか? 右のサブツリーから? 再帰。
最初に、ツリー内のすべてのノードが 2 つまたは 0 つの子を持つことが保証されている場合に問題を解決します。一部のノードに子が 1 つしかない場合は、少し注意が必要です。
ノート
記事では、ソリューションの効率/実行時間を分析する必要はありません (これは、将来のプロジェクトで必要になります)。しかし、その正しさを分析してください。つまり、アルゴリズムが正しい理由を明確に説明してください。