100. 相同的樹

• 思路
  • example
  • 遞歸，前/后序
• 復雜度. 時間：O(n), 空間: O(n)

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def traversal(root1, root2):
            if root1 == None and root2 == None:
                return True 
            if root1 == None and root2 != None:
                return False 
            if root1 != None and root2 == None:
                return False 
            if root1.val != root2.val:
                return False 
            left_result = traversal(root1.left, root2.left)
            right_result = traversal(root1.right, root2.right)
            return left_result and right_result 
        return traversal(p, q) 

• 優(yōu)化

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def traversal(root1, root2):
            if root1 == None and root2 == None:
                return True 
            if root1 == None and root2 != None:
                return False 
            if root1 != None and root2 == None:
                return False 
            if root1.val != root2.val:
                return False 
            return traversal(root1.left, root2.left) and traversal(root1.right, root2.right)
        return traversal(p, q)  

572. 另一棵樹的子樹

• 思路
  • example
  • isSameTree(root1, root2)
  • 注意root為None的情況
• 復雜度. 時間：O(), 空間: O()

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def isSameTree(root1, root2):
            if not root1 and not root2:
                return True 
            if (not root1 and root2) or (root1 and not root2):
                return False
            if root1.val != root2.val:
                return False 
            return isSameTree(root1.left, root2.left) and isSameTree(root1.right, root2.right)
        if root == None and subRoot:
            return False
        return isSameTree(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

• 轉(zhuǎn)化為數(shù)組, KMP 匹配
  • 前序遍歷
  • 注意None也要加入數(shù)組比較
• 復習KMP
  • s = 'abcabcabd'
  • p = 'abcabd' (模式串）
    • next[i]: 模式串最長"公共"前后綴長度, e.g., next[4] = 2, abcabd
      • 前綴： ..., i, 不包括0th位置
      • 后綴：0,1,..., 不包括ith位置
      • next數(shù)組計算

nxt = [0] * len(p)
slow, fast = 0, 1
while fast < len(p):
    if p[slow] == p[fast]:
        nxt[fast] = nxt[fast-1] + 1
        slow += 1
        fast += 1
    elif slow != 0:
        slow = nxt[slow-1]
    else:
        nxt[fast] = 0
        fast += 1

• KMP main code

i, j = 0, 0
while i < len(s):
    if s[i] == p[j]:
        i += 1
        j += 1
    elif j != 0:
        j = nxt[j-1]
    else:
        i += 1
    if j == len(p):
        Done

• 子樹 main code

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def getNext(p):
            nxt = [0] * len(p)
            slow, fast = 0, 1
            while fast < len(p):
                if p[slow] == p[fast]:
                    nxt[fast] = slow + 1
                    slow += 1
                    fast += 1
                elif slow != 0:
                    slow = nxt[slow-1]
                else:
                    nxt[fast] = 0
                    fast += 1
            return nxt 

        def kmp(s, p):
            nxt = getNext(p)
            i, j = 0, 0
            while i < len(s):
                if s[i] == p[j]:
                    i += 1
                    j += 1
                elif j != 0:
                    j = nxt[j-1]
                else:
                    i += 1
                if j == len(p):
                    return True  
            return False

        def getArray(root): # recursive
            def preorder(root):
                if root == None:
                    path.append('*')
                    return 
                path.append(root.val)
                preorder(root.left)
                preorder(root.right)
            path = []
            preorder(root) 
            return path

        def getArray2(root): # iterative
            cur, stack = root, []
            res = []
            while cur or stack:
                if cur:
                    stack.append(cur)
                    res.append(str(cur.val))
                    cur = cur.left
                else:
                    res.append('*')
                    node = stack.pop()
                    cur = node.right 
            res.append('*') # !!!
            return res

        nums1 = getArray(root)
        nums2 = getArray(subRoot)
        return kmp(nums1, nums2)