12

二分木 T2 が二分木 T1 のサブツリーであるかどうかを調べたい。T2 と T1 の文字列表現は、事前順序および順序どおりのトラバーサルを使用して作成できることを読みました。T2 文字列が T1 文字列の部分文字列である場合、T2 は T1 の部分木です。

私はこの方法に少し混乱しており、その正しさについて確信が持てません。

ウィキから: 「ツリー T のサブツリーは、T のノードと T のすべての子孫で構成されるツリーです。」

次の例では:

T2:
  1
 / \
2   3

T1:
  1
 / \
2   3
     \
      4

T2 と T1 の文字列を作成すると、次のようになります。

preorder T2: "1,2,3"
preorder T1: "1,2,3,4"
inorder T2: "2,1,3"
inorder T1: "2,1,3,4"

T2 文字列は T1 の部分文字列であるため、上記の部分文字列一致方法を使用すると、T2 は T1 の部分木であると結論付ける必要があります。

ただし、定義上、T2 は T1 のサブツリーであってはなりません。これは、T1 のルート ノードの子孫がすべて含まれているわけではないためです。

ここに関連する議論があり、方法が正しいと結論づけているようです。

ここで何か不足していますか？

4

6 に答える 6

8

非常に興味深い質問です。あなたは正しいようです。あなたが言及した問題は、数学（グラフ理論）とコンピューターサイエンスのサブツリーの定義が異なるために発生すると思います。グラフ理論では、T2 は T1 の適切なサブツリーです。

于 2013-05-05T05:21:31.820 に答える
7

これを本「Cracking the Coding Interview」から入手したと仮定すると、著者は、同じ値を持つノードを区別するには、null 値も出力する必要があるとも述べています。

これにより、サブツリーの定義に関する問題も解決されます（本にも記載されているように正しいです）

事前注文 T2: "1, 2, null, null, 3, null, null" 事前注文 T1: "1, 2, null, null, 3, null, 4, null, null" inorder T2: "null, 2, null, 1、null、3、null" inorder T1: "null、2、null、1、null、3、null、4、null"

ご覧のとおり、T2 は T1 のサブツリーではありません。

于 2014-09-28T18:59:34.770 に答える
0

ツリーのサブツリーの定義は、文字列のサブストリングの定義と同じである必要があります。次のように考えてください: 1. サブストリングには、begins-with、contains、ends-with があります。2. Tree も同じ定義を持つ必要がありますが、Tree データ構造に合わせて一般化されている必要があります。3. 一般化は、ストリングの 1 次元からツリーの 2 次元へです。

于 2014-01-29T08:58:03.660 に答える
0

私は同じ本を読んでいて、その解決策も疑っています。ユーザーicepackが言及する潜在的な解釈に該当しない別の反例を思いつきました（必ずしもすべての子孫を必要としないサブツリーの）。

次のツリーを検討してください

T2:
  B
 / \
A   C

T1:
    C
   / \
  B   C
 /
A

予約注文 T2: 'BAC'
予約注文 T1: 'CBAC' 注文
T2: 'ABC'注文 T1
: 'ABCC'

繰り返しになりますが、T2 文字列は対応する T1 文字列の部分文字列ですが、T2 は決して T1 の部分木ではありません。おそらく、著者は重複を除外し、サブツリーの定義を具体的に述べていたので、それは正しいかもしれませんが、その情報を除外すると、それを間違った解決策と見なすしかありません。

于 2014-02-19T18:49:43.247 に答える
-2

Na...このアプローチは正しくありません。なぜなら、異なるツリーが同じトラバーサルを持つ可能性があるからです。たとえば、ここで与えられた例では、ツリーは

         26
        /   \
      10     3
    /    \     \
  4      6      3
   \
    30

候補サブツリーは

10
/ \
4 6
\
30

と

30
/ \
4 10
\
6

4,30,10,6 と同じ順序でトラバーサルしますが、2 番目のものはサブツリーではありません

于 2014-07-09T06:12:57.217 に答える