## 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.

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.

## Solutions

### 1. Direct

# Time: O(logn*logn)
# Space: O(n)
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
queue = collections.deque()
queue.append(s)
while queue:
node = queue.popleft()
if not node:
continue
if node.val == t.val:
if self.is_equal(node, t):
return True
queue.append(node.left)
queue.append(node.right)
return False

def is_equal(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
if s.val != t.val:
return False

if self.is_equal(s.left, t.left) and \
self.is_equal(s.right, t.right):
return True
else:
return False

# 176/176 cases passed (248 ms)
# Your runtime beats 65.75 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.2 MB)


果然手写太冗余了，参考人家全是递归的做法。

# Time: O(s*t)
# Space: O(s)
class Solution:
def isSubtree(self, s, t):
if self.isMatch(s, t): return True
if not s: return False
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

def isMatch(self, s, t):
if not(s and t):
return s is t
return (s.val == t.val and
self.isMatch(s.left, t.left) and
self.isMatch(s.right, t.right))
# 176/176 cases passed (240 ms)
# Your runtime beats 70.66 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.4 MB)


### 2. String

中序访问成字符串，然后比较，因为数值可能有多位的区别，可以在中间加上一些字符表示区别，比如说中间间隔用#，空用$。 # Time: O(s+t) # Space: O(s+t) class Solution: def isSubtree(self, s, t): return self.convert(t) in self.convert(s) def convert(self, s): return "^" + str(s.val) + "#" + self.convert(s.left) + self.convert(s.right) if s else "$"
# 176/176 cases passed (72 ms)
# Your runtime beats 92.96 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.5 MB)


### 3. 神奇做法

还没来得及看，感觉很复杂。

class Solution:
def isSubtree(self, s, t):
# from hashlib import sha256
from hashlib import sha1
def hash_(x):
# S = sha256()
# S.update(x)
# return S.hexdigest()
m = sha1()
m.update(str.encode(s))
return m.hexdigest()

def merkle(node):
if not node:
return '#'
m_left = merkle(node.left)
m_right = merkle(node.right)
node.merkle = hash_(m_left + str(node.val) + m_right)
return node.merkle

merkle(s)
merkle(t)
def dfs(node):
if not node:
return False
return (node.merkle == t.merkle or
dfs(node.left) or dfs(node.right))

return dfs(s)