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.

class Solution:
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        def issame(a,b):
            if a is None and b is None:
                return True
            if a is None or b is None:
                return False
            if a.val!=b.val:
                return False
            return issame(a.left,b.left) and issame(a.right,b.right)
        if s is None:
            return False
        if issame(s,t):
            return True
        return self.isSubtree(s.left,t) or self.isSubtree(s.right,t)