題目連結:
題目意譯:
給定兩個非空二元樹 s 以及 t,判斷 t 是否擁有與 s 的其中一棵子樹同樣的結構以及同樣的節點值。s 的一棵子樹為一個根節點以及該節點的所有子節點形成的樹。s 本身也應視為自身的一棵子樹。
範例測資:
範例 1:
給定樹 s:
3
/ \
4 5
/ \
1 2
給定樹 t:
4
/ \
1 2
回傳真(True),因為 t 擁有與 s 的某一棵子樹同樣的結構以及節點值。
範例 2:
給定樹 s:
3
/ \
4 5
/ \
1 2
/
0
給定樹 t:
4
/ \
1 2
回傳假(False)。
解題思維:
先判斷 s 與 t 是否同一棵樹(按照
這題的做法),如果是的話就回傳真;反之,遞迴判斷 s 的左子樹與 t 的關係以及 s 的右子樹與 t 的關係,如果有任何一邊找到一棵子樹與 t 相同則為真;反之,為假。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。