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

## 解法¶

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def isSubtree(self, s, t):
s_nodes_str = self._preorder(s, True)
t_nodes_str = self._preorder(t, True)
return t_nodes_str in s_nodes_str

def _preorder(self, root, is_left):
if root is None:
if is_left:
return 'left_none'
else:
return 'right_none'

# 开头和结尾的 # 以及 left_none 和 right_none 是为了便于验证树的结构是否一致
return '#{}-{}-{}#'.format(
root.val,
self._preorder(root.left, True),
self._preorder(root.right, False)
)
```