572.md

572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4 
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.

my thoughts:

1. travel tree s; when s-n.val == t-root.val, check if s-n matches t. This can be a O(n*m) time.

my solution:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        self.cand = []
        self.res = False
        def trav_s(s, t):
            if not s:
                return
            if s.val == t.val:
                self.cand.append(s)
            trav_s(s.left, t)
            trav_s(s.right, t)
        trav_s(s, t)
        def check(s, t):
            
            if not s and not t:
                return True
            if s and t and s.val == t.val:
                return (check(s.left, t.left) and check(s.right, t.right))
            self.res = False
            return False
        while self.cand and not self.res:
            n = self.cand.pop()
            self.res = check(n, t)
        return self.res
            

my comments:

solution accepted, 252ms run time

from other ppl's solution:

1. the recusion can be more concise, 85ms:
class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if s:
            if t:
                if s.val == t.val and self.isStrictSubTree(s.left, t.left) and self.isStrictSubTree(s.right, t.right):
                    return True
                else:
                    if self.isSubtree(s.left, t):
                        return True
                    if self.isSubtree(s.right, t):
                        return True
#                    print s.val, t.val
                    return False
            else:
#                print s.val, "T-None"
                return False
        else:
            if t:
#                print t.val, "S-None"
                return False
            else:
#                print "TS-None"
                return True

    def isStrictSubTree(self, s, t):
        if s and t and s.val == t.val and self.isSubtree(s.left, t.left) and self.isSubtree(s.right, t.right):
            return True
        if s is None and t is None:
            return True
        return False
		
2. can use preorder -> substring approach, 92ms:
class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        s_order = []
        self.preorder(s, s_order)
        
        t_order = []
        self.preorder(t, t_order)
        
        s_str = ',' + ','.join(s_order)
        t_str = ',' + ','.join(t_order)
        
        return t_str in s_str

    def preorder(self, node, res):
        if not node:
            res.append('#')
            return
        res.append(str(node.val))
        self.preorder(node.left, res)
        self.preorder(node.right, res)