给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
给定的树 t：
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
1
2
3
4
5
6
7
| 3
/ \
4 5
/ \
1 2
/
0
|
给定的树 t：
返回 false。
题解
仅作为KMP的练习，非最优解
先将两棵树序列化（这里采用先序遍历），再利用 KMP 判断 t 是否为 s 的子串。
Java
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class Code_45_SubtreeOfAnotherTree {
public static String getPreorderString(TreeNode treeNode) {
if (treeNode == null) return "#";
String tmpResult = "_" + treeNode.val + "_" + getPreorderString(treeNode.left);
tmpResult += "_" + getPreorderString(treeNode.right);
return tmpResult;
}
public static int[] getNextTable(String pattern) {
int len = pattern.length();
int lp = -1, rp = 0;
int[] nextTable = new int[len];
nextTable[0] = -1;
while (rp < len - 1) {
if (lp == -1 || pattern.charAt(lp) == pattern.charAt(rp)) {
nextTable[++rp] = ++lp;
} else {
lp = nextTable[lp];
}
}
return nextTable;
}
public static boolean isSubtree(TreeNode s, TreeNode t) {
String serializedS = getPreorderString(s);
String serializedT = getPreorderString(t);
int sCur = 0, tCur = 0;
int sLen = serializedS.length();
int tLen = serializedT.length();
int[] nextTable = getNextTable(serializedT);
while (sCur < sLen && tCur < tLen) {
if (serializedS.charAt(sCur) == serializedT.charAt(tCur)) {
sCur++;
tCur++;
} else {
if (tCur == 0) sCur++;
else tCur = nextTable[tCur];
}
}
return tCur == tLen;
}
}
|
Python
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class SubTreeOfAnotherTree:
def get_preorder_string(self, tree_node: TreeNode):
if not tree_node: return '#'
tmp_str = '_' + str(tree_node.val) + '_' + self.get_preorder_string(tree_node.left)
tmp_str += '_' + self.get_preorder_string(tree_node.right)
return tmp_str
def get_next_table(self, pattern: str):
lp, rp = -1, 0
length = len(pattern)
next_table = [0] * length
next_table[0] = -1
while rp < length - 1:
if pattern[lp] == pattern[rp] or lp == -1:
lp += 1
rp += 1
next_table[rp] = lp
else:
lp = next_table[lp]
return next_table
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
serialized_s = self.get_preorder_string(s)
serialized_t = self.get_preorder_string(t)
s_len = len(serialized_s)
t_len = len(serialized_t)
s_cur, t_cur = 0, 0
next_table = self.get_next_table(serialized_t)
while s_cur < s_len and t_cur < t_len:
if serialized_s[s_cur] == serialized_t[t_cur]:
s_cur += 1
t_cur += 1
else:
if t_cur == 0:
s_cur += 1
else:
t_cur = next_table[t_cur]
return t_cur == t_len
|
Go
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func getPreorderString(treeNode *TreeNode) string {
if treeNode == nil {
return "#"
}
tmpStr := "_" + strconv.Itoa(treeNode.Val) + "_" + getPreorderString(treeNode.Left)
tmpStr += "_" + getPreorderString(treeNode.Right)
return tmpStr
}
func getNextTable(pattern string) []int {
lp, rp := -1, 0
length := len(pattern)
nextTable := make([]int, length)
nextTable[0] = -1
for rp < length-1 {
if lp == -1 || pattern[lp] == pattern[rp] {
lp++
rp++
nextTable[rp] = lp
} else {
lp = nextTable[lp]
}
}
return nextTable
}
func isSubtree(s *TreeNode, t *TreeNode) bool {
serializedS := getPreorderString(s)
serializedT := getPreorderString(t)
sCur, tCur := 0, 0
sLen := len(serializedS)
tLen := len(serializedT)
nextTable := getNextTable(serializedT)
for sCur < sLen && tCur < tLen {
if serializedS[sCur] == serializedT[tCur] {
sCur++
tCur++
} else {
if tCur == 0 {
sCur++
} else {
tCur = nextTable[tCur]
}
}
}
return tCur == tLen
}
|
奇淫巧技
LeetCode @洪世贤：
没有什么是 Python 一行解决不了的
Python 的诱惑？
1
2
3
| class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
return str(s).find(str(t)) != -1
|