天天看點

03-樹1 樹的同構 (25分)

給定兩棵樹T1和T2。如果T1可以通過若幹次左右孩子互換就變成T2,則我們稱兩棵樹是“同構”的。例如圖1給出的兩棵樹就是同構的,因為我們把其中一棵樹的結點A、B、G的左右孩子互換後,就得到另外一棵樹。而圖2就不是同構的。

03-樹1 樹的同構 (25分)
03-樹1 樹的同構 (25分)

現給定兩棵樹,請你判斷它們是否是同構的。

輸入格式:

輸入給出2棵二叉樹樹的資訊。對于每棵樹,首先在一行中給出一個非負整數NN (\le 10≤10),即該樹的結點數(此時假設結點從0到N-1N−1編号);随後NN行,第ii行對應編号第ii個結點,給出該結點中存儲的1個英文大寫字母、其左孩子結點的編号、右孩子結點的編号。如果孩子結點為空,則在相應位置上給出“-”。給出的資料間用一個空格分隔。注意:題目保證每個結點中存儲的字母是不同的。

輸出格式:

如果兩棵樹是同構的,輸出“Yes”,否則輸出“No”。

輸入樣例1(對應圖1):

8

A 1 2

B 3 4

C 5 -

D - -

E 6 -

G 7 -

F - -

H - -

8

G - 4

B 7 6

F - -

A 5 1

H - -

C 0 -

D - -

E 2 -

輸出樣例1:

Yes

輸入樣例2(對應圖2):

8

B 5 7

F - -

A 0 3

C 6 -

H - -

D - -

G 4 -

E 1 -

8

D 6 -

B 5 -

E - -

H - -

C 0 2

G - 3

F - -

A 1 4

輸出樣例2:

No

03-樹1 樹的同構 (25分)
03-樹1 樹的同構 (25分)