前往
大廳
主題

LeetCode - 572. Subtree of Another Tree 解題心得

Not In My Back Yard | 2020-11-21 00:00:02 | 巴幣 0 | 人氣 135

題目連結:


題目意譯:
給定兩個非空二元樹 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 相同則為真;反之,為假。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作