2021-02-07：给定两棵二叉树的头节点head1和head2，如何判断head1中是否有某个子树的结构和head2完全一样？
福哥答案2021-02-07：
对head1和head2序列化为str1和str2。然后用kmp算法去判断str2是否是str1的子串。如果是，head2是子树；如果不是，head2不是子树。
代码用golang编写，代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
root := &TreeNode{}
root.Val = 1
root.Left = &TreeNode{}
root.Left.Val = 2
root.Right = &TreeNode{}
root.Right.Val = 3
root.Left.Right = &TreeNode{}
root.Left.Right.Val = 4
root.Right.Left = &TreeNode{}
root.Right.Left.Val = 5
fmt.Println(IsSubTree(root, root.Right))
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//序列化
func serialize(head *TreeNode) string {
ansVal := ""
ans := &ansVal
process(head, ans)
return (*ans)[1:]
}
func process(head *TreeNode, ans *string) {
if head == nil {
*ans = ",N"
return
}
*ans = fmt.Sprintf(",%d", head.Val)
process(head.Left, ans)
//*ans = fmt.Sprintf(",%d", head.Val)
process(head.Right, ans)
//*ans = fmt.Sprintf(",%d", head.Val)
}
func getNextArr(m string) []int {
mLen := len(m)
if mLen == 1 {
return []int{-1}
}
ret := make([]int, mLen)
ret[0] = -1
cn := 0
for i := 2; i < mLen; i {
if m[i] == m[cn] {
cn
ret[i] = cn
i
} else if cn > 0 {
cn = ret[cn]
} else {
ret[i] = 0
i
}
}
return ret
}
//求子串位置
func kmp(s string, m string) int {
sLen := len(s)
mLen := len(m)
if sLen < mLen {
return -1
}
next := getNextArr(m)
x := 0
y := 0
for x < sLen && y < mLen {
if s[x] == m[y] {
x
y
} else if next[y] >= 0 {
y = next[y]
} else {
x
}
}
if y == mLen {
return x - y
} else {
return -1
}
}
//求是否是子树
func IsSubTree(head1 *TreeNode, head2 *TreeNode) bool {
if head2 == nil {
return true
}
if head1 == nil {
return false
}
if kmp(serialize(head1), serialize(head2)) >= 0 {
return true
} else {
return false
}
}执行结果如下：
在这里插入图片描述
