推 NTHUlagka: 大師 為啥中序不行啊 這是什麼性質阿沒查到02/28 21:27
因為中序走訪不同的樹可能會跑出一樣的結果，這樣兩個樹HASH出來會一樣但是
樹實際上並不一樣。
1 3
/ \
2 2
/ \
3 1
上面兩個樹用中序打印出來都是321但是實際上卻是不同的樹。
用前序打印會是123 321
用後序打印會是321 123
我記得資結有一個章節有講用「前序+中序」或是「後序+中序」才可以反推得到
一個唯一的樹。
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677592171.A.936.html
推 zhtw: 大師 02/28 21:50
推 HccrtZ: 大師 02/28 21:52
推 abcd991276: 大師 02/28 21:53
推 NTHUlagka: 那個章節是講要用兩個序才能得到唯一樹 可是這題卻能 02/28 21:58
→ NTHUlagka: 用前序或後序 這是有什麼保證嗎 02/28 21:58
→ NTHUlagka: 我這題是map的key存兩個序concat 但看到討論區說可以 02/28 21:58
→ NTHUlagka: 用一個 蠻好奇理論是啥 02/28 21:58
那個章節是給定序列反推樹所以要兩個 這個不用反推阿 所以一個就好
推 NTHUlagka: 但這題也是把樹轉成序列 然後依照序列相同來視為是相 02/28 22:07
→ NTHUlagka: 同樹 這樣不就有反推的意謂了 代表你可以在只給一個前 02/28 22:07
→ NTHUlagka: 序或後序的序列決定出一個唯一的樹狀結構 02/28 22:07
沒有阿 我們又沒有要反推 因為前序和後序打印出來的一定唯一 中序打印上面那種例子
會出現問題
推 NTHUlagka: 前後序有唯一嗎 上述的例子是中序不同的例子 但應該可 02/28 22:30
→ NTHUlagka: 以列出其他例子是前序或後序一樣但樹狀結構不相同吧？ 02/28 22:30
推 NTHUlagka: 等等還是因為你有加空格才有保證唯一？ 02/28 22:35
→ Rushia: 有唯一阿 打印的時候包含空格 02/28 22:35
推 idiont: 好神奇的性質 給前序+後序沒辦法找到唯一的樹 但是加了空 02/28 22:45
→ idiont: 格後只要其中一個就能唯一 02/28 22:45
[0,0,0,0,null,null,0,null,null,null,0]
0
/ \
0 0
/ \
0 0
\
0
, = 空格
,,0,, <= [0]
,,0,,,0,, <= [0,0,null]
,,0,, <= [0]
,,0,,,0,, <= [0,null,0]
,,0,,,0,,,0,, <= [0,null,0,null,null,null,0]
,,0,,,0,,,0,,,0,,,0,,,0,, <= [0,0,0,0,null,null,0,null,null,null,0]
中序打印出來 [0,0,null] 會和 [0,null,0] 一樣
※ 編輯: Rushia (122.100.75.86 臺灣), 02/28/2023 22:53:32
推 NTHUlagka: 嗯嗯喔喔是因為有空格才保證唯一 如果沒有好像就不行 02/28 22:59
→ NTHUlagka: 我看討論區又有人說如果中序有定義好好像也可以 02/28 22:59