バイナリツリーの結合

Question

inorderとpreorderのトラバーサルが与えられたバイナリツリーのセットがあり、指定されたセット内の別のツリーのサブツリーが存在しないツリーがあるとします。ここで、別のバイナリツリーQが与えられます。これは、与えられたセットからバイナリツリーを結合することによって形成できるかどうかを確認します（セット内の各ツリーを一度に結合する必要があります）。その集合の任意の木を別の木の任意の頂点に引っ張り、その結果の木も二分木であるようにする。

LCA（最小共通祖先）を使用してこれを行うことはできますか？解決するために特別なデータ構造が必要ですか？

Answer 1

私はバイナリツリー構造で十分だと思います。他の特別なデータ構造は必要ないと思います。

そして、LCAをどのように使用するのか分かりません。限り、私の知る限り、LCAは同じ木の2つのNODESのための最も低い共通の祖先を知るために使用されます。それは2本の木を比較するのに役立たないでしょう。 （これはQが形成できるかどうかを調べるために行うものです）

ツリーのセットから作成できるかどうかをチェックする必要があるツリーQは、トップダウンのアプローチを採用します。基本的にQを、その集合から形成される可能性のある樹木と比較する。

論理： Q.rootがセット内のツリーのルート（A、B、C .... Z ...）と一致しない場合、解決策はありません。

Q.rootがツリールート（たとえばA）に一致し、対応する子をチェックし、Aを使用済み/訪問済みとしてマークするとします。

Qの子どものすべてがAの対応する子と一致する場合にのみ、私たちの解決策ではAを続ける必要があります（私は深さ優先トラバーサルを行います）。 、Breadth Firstも同様に機能します）。

バイナリツリーを維持する必要があるため、セットから新しいツリーを追加することができます（つまり、Aのリーフノードにのみ新しいルート（ツリーB）を追加します）。 Bがどこに追加されたのか追跡してください。

Aと同じ子どもの比較と同じチェックを繰り返します。一致しない場合はBを削除し、Bが追加された場所にCツリーを追加しようとします。

私たちはID内のノードがなくなるまでこれをやり続けます（IDENTICAL MATCHが必要な場合を除いて、私たちが持っているもの以外の他のツリーの組み合わせを試してみましょう。 。

長い冗長な回答のお詫び。 （私の擬似コードは書くのが難しく、説明するためにコメントをつけるのが難しいと感じます）。

これが役に立ちます。

他の解決策：木の数が比較的少ない場合にのみ試みてください：ツリーのすべてのセットを作成する（最初は2秒後に3秒... N）、そして形成されたツリーをチェックする彼らはQ. 比較部と同一である場合、ここで参照することができます：どのように我々はINORDER与えられ、行きがけのトラバースから次の子を見つけることができるように http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/