題目解釋
給定兩個 binary tree root
和 subRoot
的根,
如果 root
的子樹具有相同的結構和 subRoot
的節點值,則傳回 true,
否則傳回 false。
子樹定義:
- Binary tree 的子樹是由樹中的一個節點和該節點的所有後代 (descendants) 組成的樹。
- 樹也可以被視為其自身的子樹。
範例
- 輸入:
root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
- 輸出:
True
subRoot
是 root
的子樹。
最佳解法
Traverse 整棵 root
,然後使用 _isSameTree
判定兩樹是否相同。
關於
_isSameTree
的實作請回頭看:【Leetcode 筆記】100. Same Tree
注意,最後 return 的條件式是用 or
,
因為 root
的左子樹或右子樹只要跟 subtree
相同就算是 ok。
程式碼
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def _isSameTree(p, q):
if (not p) and (not q):
return True
if (p and not q) or (not p and q) or (p.val != q.val):
return False
else:
return _isSameTree(p.left, q.left) and _isSameTree(p.right, q.right)
if not root:
return False
if _isSameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
時間複雜度
O(n * m)
,因為對於 root 中的每個節點,都可能呼叫 _isSameTree
檢查是否與 subRoot
相符。
空間複雜度
O(h)
,h 是 root
的高度,長的平均的話最好情況是 O(log n)
。
結語
雙重遞迴,就看玩的 6 不 6… 。
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26