動機

老實地分成兩個dfs

Problem

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

 

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]Output: false

 

Constraints:

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

Sol: WA

一開始想著把

  • 比對
  • 走訪

一起做完，最後就悲劇了，比對要一次比對完，不然比對的對象會被拆掉，像

[3,4,5,1,null,2]
[3,1,2]

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not t and not s:
            return True
        elif not t or not s:
            return False
        else:
            ret = self.isSubtree(s.left,t) or self.isSubtree(s.right,t)
            if s.val == t.val:
                ret = ret or self.isSubtree(s.left,t.left) and self.isSubtree(s.right,t.right)
            return ret

Sol

class Solution:
    def equal(self,s,t):
        if not t and not s:
            return True
        elif not t or not s:
            return False
        else:
            return s.val == t.val and self.equal(s.left,t.left) and self.equal(s.right,t.right)
    def f(self,s,t):
        if not s:
            return False
        else:
            return self.equal(s,t) or self.f(s.left,t) or self.f(s.right,t)
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        return self.f(s,t)

Sol: preorder

走preorder找substring，不過要注意像

[12,1]
[2,1]

這種，要加個符號區分點與點

class Solution:
    # dont integrate two recursion into one
    def pre(self,s,t):
        if not s:
            t.append('y')
            return t
        else:
            t.append("x"+str(s.val))
            return self.pre(s.right,self.pre(s.left,t))
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        s = self.pre(s,[])
        t = self.pre(t,[])
        print(s,t)
        s = ','.join(s)
        t = ','.join(t)
        print(s,"::",t)
        return t in s