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
    }
}