java - 二分木には別の木が含まれていますか?

Question

今日のインタビューでこの質問をされましたが、次のようになります。

「1 つのバイナリツリーが別のバイナリツリー内に含まれているかどうかを判断します (contains はノードの構造と値の両方を意味します)」

次のアプローチを考えました。

大きなツリーを次のように平坦化します。

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}}

(私は実際にこのためのコードを書きました。{-}空の左または右のサブツリーを意味し、各サブツリーは {} 括弧で囲まれています)

小さいサブツリーの場合、次のパターンに一致させる必要があります。

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}}

ここで{.*}、空または空でないサブツリーを示します。

当時は、これは Java での正規表現パターンマッチングの問題にすぎないと思っていましたが、だまされました。実際、私は問題を変換しただけだと感じています (別の怪物から 1 つの怪物を作成しました)。

これらのパターンに一致する単純な正規表現ワンライナーはありますか? この問題を解決するための他のアプローチがある可能性があり、これが最善の方法ではない可能性があることを理解しています。これが解決可能かどうかは疑問です。

score 1 · Accepted Answer

インタビュアーが「別のバイナリツリー内に含まれている」とは正確に何を意味していたのかはわかりません。インタビュアーが A が B のサブツリーであるかどうかを確認する方法を求めていた場合、正規表現をまったく必要としない 1 つの方法を次に示します。

null リーフを含めたい理由は、複数のノードが同じ値を持つ場合、preorder と inorder では不十分な場合があるためです。次に例を示します。

          A
      A       A
   B     B       C
 C         D       B
D           C       D

これをチェックアウトすることもできます：

また、バイナリツリーの preorder および inorder トラバーサルの詳細については、これをお読みください。

さて、彼がサブツリーだけを意味していなかったとしたら、インタビュアーが「部分」によって何を意味したかによって、問題はより複雑になる可能性があります. 質問をサブグラフ同型問題 (ツリーはグラフのサブセットにすぎません) と見なすことができ、これは NP 完全です。

ツリーはグラフよりもはるかに制限されており、単純であるため、より良いアプローチが存在する可能性があります。

4 に答える 4