題目出處
難度
easy
個人範例程式碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
# end of recursion
if not root:
return False
# define
if self.is_same_tree(root, subRoot):
return True
# split
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def is_same_tree(self, root, subroot):
# end of recursion
if not root and not subroot:
return True
if not root or not subroot: # only one side left
return False
if root.val != subroot.val:
return False
return self.is_same_tree(root.left, subroot.left) and self.is_same_tree(root.right, subroot.right)
算法說明
原本的 is_sub_tree,就已經可以幫助我們把大題目拆成小題目了,
我們只需要再多補上一個,比較兩個 tree 是否相同的函數即可。
input handling
if not root,return False (上層只要有一次 True 即可,因此用 or 比較其他答案)
Boundary conditions
用 not root,來判斷 Tree 的結尾。
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python | 內含 BFS 模板 #重要題型 | |