# 572. Subtree of Another Tree 另一棵树的子树

@TOC

## # 题目描述

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

## # 解题方法

### # 方法一：先序遍历

Java 代码如下：

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
StringBuilder spre = new StringBuilder();
StringBuilder tpre = new StringBuilder();
public boolean isSubtree(TreeNode s, TreeNode t) {
preOrder(s, spre.append(","));
preOrder(t, tpre.append(","));
System.out.println(spre.toString());
System.out.println(tpre.toString());
return spre.toString().contains(tpre.toString());
}
public void preOrder(TreeNode root, StringBuilder str){
if(root == null){
str.append("#,");
return;
}
str.append(root.val).append(",");
preOrder(root.left, str);
preOrder(root.right, str);
}
}
``````

### # 方法二：DFS + DFS

1. 当前两棵树相等；
2. 或者，s 的左子树和 t 相等
3. 或者，s 的左子树和 t 相等

1. 当前两个树的根节点值相等
2. 并且，s 的左子树和 t 的左子树相等
3. 并且，s 的左子树和 t 的右子树相等

Python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
if not s and not t:
return True
if not s or not t:
return False
return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

def isSameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
``````

### # 方法三：BFS + DFS

Python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
if not s and not t:
return True
if not s or not t:
return False
que = collections.deque()
que.append(s)
while que:
node = que.popleft()
if not node:
continue
if self.isSameTree(node, t):
return True
que.append(node.left)
que.append(node.right)
return False

def isSameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
``````

## # 日期

2017 年 5 月 9 日 2018 年 10 月 19 日 —— 自古逢秋悲寂寥，我言秋日胜春朝 2018 年 11 月 21 日 —— 又是一个美好的开始 2020年 5 月 7 日 —— 先把工作忙完，再搞其他的