给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
自我解答
思考了很久，考虑了多个方案，但最终都没成功，挺沮丧的。不过看到评论好多都是在说这道题好难，不应该是简单题后,
心理就平衡多了。。。。
1、如果要进行匹配，那么就一定需要对二叉树进行遍历，那么选择什么遍历方式呢？
对比发现，先序遍历似乎是最合适的，因为如果t是s的子树，那么t的先序遍历序列一定是在 s 的先序遍历序列里，
那么是否可以通过这样改造成两个序列匹配呢？
容易发现是不行的，如序列ABC, 可以有很多种结构。 所以这种方案被否定掉了。
2、最容易的肯定就是像字符串朴素做法那样，但那样时间复杂度太高了。
怎么能像 kmp 算法那样，遍历 s 树时，不回溯呢？ 如果要像 kmp 那样只回溯 t, 关键是要找到 “前后重合”，
无奈我找的好辛苦，最终还是没找着，放弃了。二叉树不像列表那样是线性结构的，“前后重合” 要求 结构、数值
都一样，然而这一切都要先序遍历的过程中进行，我尝试设置一些变量去整合，递归，非递归方式，都太乱了，无果
题解
其中一个题解就是将两个树先序遍历序列进行 kmp，但是一个序列的真实结构是不确定的，怎么可以直接匹配序列呢？
可以优化一下，变成可唯一确定结构的序列: 把孩子为空也表示在序列中，就像力扣二叉树测试用例的描述那样。
如 A 的左右孩子分别为 None, B, 正常先序序列为 AB，无法确定结构，但如果 是 [A, None, B],
就可以完全确定结构了。
唉，就好像是在走迷宫一样，你并不能确定这条路走下去是死路还是出路，只能凭当时的信息去评估价值，
当时的信息就是: 这是一道简单题，不应该这么难，这条路继续下去很可能就是钻牛角尖了。
也许这就是人生吧，看的多了，走的弯弯绕绕多了，信息就多了，信息多了，判断就更准了。
自己用python实现了
class Solution2:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not t: return True
sorders, torders = [], []
self.load_preorders(s, sorders)
self.load_preorders(t, torders)
s_len, t_len = len(sorders), len(torders)
tnexts = self.get_nexts(torders, t_len)
i, j = 0, 0
while i < s_len:
if j == -1 or sorders[i] == torders[j]:
if j == t_len - 1:
return True
i += 1
j += 1
else:
j = tnexts[j]
return False
def get_nexts(self, orders, length):
nexts = [0] * length
nexts[0] = -1
i, j = 1, 0
while i < length - 1:
if j == -1 or orders[i] == orders[j]:
i += 1
j += 1
nexts[i] = j
else:
j = nexts[j]
return nexts
def load_preorders(self, node: TreeNode, orders: List[int]) -> None:
if not node:
orders.append(None)
return
orders.append(node.val)
self.load_preorders(node.left, orders)
self.load_preorders(node.right, orders)
kmp 用在这里，代码量还是太大了，我想到了使用内置函数 str.find 代替的方案：
关键是把“先序序列” 转换成可以使用这个函数的字符串，我使用 "," 间隔开,
但是像 "12,None,None" 和 "2,None,None" 这样的还是会判断成 True, 所以，遇到这种情况需要看匹配到的
位置的前一位是否是 ","
这样代码就少很多了
class Solution3:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not t: return True
sorders, torders = [], []
self.load_preorders(s, sorders)
self.load_preorders(t, torders)
sorders = ",".join(sorders)
torders = ",".join(torders)
i = 0
while True:
i = sorders[i:].find(torders)
if i == -1: return False
if i == 0 or sorders[i - 1] == ",":
return True
else:
i = i + 1
def load_preorders(self, node: TreeNode, orders: List[int]) -> None:
if not node:
orders.append("None")
return
orders.append(str(node.val))
self.load_preorders(node.left, orders)
self.load_preorders(node.right, orders)
原题链接：https://leetcode-cn.com/problems/subtree-of-another-tree