java - 順序とレベルトラバーサルから二分木を構築する

Question

順序とレベルのトラバーサルが与えられたバイナリ ツリーを構築する方法を見つける手助けが必要です。キューを使用してレベルのトラバーサルを行う必要があるため、再帰を使用してそれを行うことは可能ですか?

Answer 1

この問題にアプローチする方法は次のとおりです。逆から見ると、各ステップへのアプローチ方法を考えるのが簡単です。

      8
     / \
    4   9
   / \   \
  2   6   10
 /
1

次のものがあります。

順番に：1 2 4 6 8 9 10

レベル：8 4 9 2 6 10 1

レベル 1 - ルート

レベル トラバーサルは、ツリーの左から右、上から下へのトラバーサルです (幅優先探索と同様)。この例では、それ8がルート ノードになることがわかっています。inorder トラバーサルを見ると1 2 4 6、左側のサブツリーを9 10構成し、右側のサブツリーを構成することがわかります。したがって、次のようになります。

        8
1 2 4 6   9 10

順序を維持しながら、左と右の再帰的構築のために訪問するノードなしでレベル トラバーサルのコピーを作成します。以下の注記は、左側のツリーのステップを通過し、通過するものは次のとおりです。

レベル 2 - 左サブツリー

順番に：1 2 4 6

レベル：4 2 6 1

• 根：4
• 左のサブツリー:1 2
• 右サブツリー:6

結果：

        8
       /  9 10
      4
  2 1  \
        6

レベル 3 - 左サブツリー

順番に：1 2

レベル：2 1

• 根：2
• 左のサブツリー:1
• 右サブツリー: 空

結果：

       8
      /  9 10
     4
    / \   
   2   6
  /
 1

これで、左端までの再帰が完了したので、ツリーの右の子を処理する方法を順を追って説明できることを願っています! アルゴリズムを取得したら、2 つの異なるトラバーサルを指定してツリーを元に戻すことができるはずです。重要なのは、2 つのトラバーサルに基づいて、各再帰呼び出しでルートを決定する方法を認識することであり、残りは実行する必要があります。