題目出處
難度
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 的結尾。