题目地址：https://leetcode.com/problems/subtree-of-another-tree/#/descriptionopen in new window
题目描述
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.
题目大意
判断t 是不是 s 的一个子树。
解题方法
方法一：先序遍历
先序遍历把树转成字符串，判断是否为子串。
在当节点为空的时候给一个“#”表示，这样就能表示出不同的子树，因此只需要遍历一次就能得到结果。每次遍历到树的结尾的时候能够按照#区分，另外每个树的节点值之间用","分割。 在提交的时候又遇到一个问题，就是12和2的结果是一样的，那么我在每个遍历结果的开头位置再加上一个逗号就完美解决了。 另外注意，不要判断左右子树不为空再去遍历树，这样就不能添加上“#”了。
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);
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
方法二：DFS + DFS
要判断一个树 t 是不是另外一个树 s 的子树，那么可以判断 t 是否和树 s 的任意子树是否相等。那么就和100. Same Treeopen in new window挺像了。所以这个题的做法就是在判断两棵树是否相等的基础上，添加上任意子树是否相等的判断。
判断t 是否为 s 的子树的方式是：
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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
方法三：BFS + DFS
因为t 的根节点可能对应着 s 中的任意一个节点，那么我们使用 BFS 来遍历 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
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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发