Subtree of Another Tree

is_subtree.py

"""
Description:
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.

Examples:
Input:
tree s   3
        / \
       4   5
      / \
     1   2
tree t   4 
        / \
       1   2
Output: True

Input:
tree s   3
        / \
       4   5
      / \
     1   2
        /
       0
tree t   4 
        / \
       1   2
Output: False
"""

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def isSubtree(s, t):
    """
    :type s: TreeNode
    :type t: TreeNode
    :rtype: bool
    """
    def serialize(node):
        if node:
            return '^' + str(node.val) + serialize(node.left) + serialize(node.right)
        else:
            return '$'
    print(serialize(t), serialize(s))
    return serialize(t) in serialize(s)