package main

import (
    "encoding/json"

    "github.com/davecgh/go-spew/spew"
)

func main() {
    list := NewListNode("[1,2,null,3,4,null,5]")
    spew.Println(list)
    /*
              1
           /     \
          2        3
         / \     /   \
        4   5   6     7
       /     \   \   /
      8       9  10 11   */
    root := &TreeNode{
        Val: 1,
        Left: &TreeNode{
            Val: 2,
            Left: &TreeNode{
                Val: 4,
                Left: &TreeNode{
                    Val: 8,
                },
            },
            Right: &TreeNode{
                Val: 5,
                Right: &TreeNode{
                    Val: 9,
                },
            },
        },
        Right: &TreeNode{
            Val: 3,
            Left: &TreeNode{
                Val: 6,
                Right: &TreeNode{
                    Val: 10,
                },
            },
            Right: &TreeNode{
                Val: 7,
                Left: &TreeNode{
                    Val: 11,
                },
            },
        },
    }
    printTree(root)
    testRecursive(root)
    testTraverse(root)
}

/*测试非递归解法*/
func testTraverse(root *TreeNode) {
    spew.Println("----------- in testTraverse")
    defer spew.Println("----------- out testTraverse")
    b, _ := json.Marshal(preOrder(root))
    pre := string(b)
    b, _ = json.Marshal(midOrder(root))
    mid := string(b)
    b, _ = json.Marshal(postOrder(root))
    post := string(b)
    b, _ = json.Marshal(levelOrder(root))
    level := string(b)
    spew.Println("pre:", pre)
    spew.Println("mid:", mid)
    spew.Println("post:", post)
    spew.Println("level:", level)
    tmp := NewTreeNode(pre, mid, 1, false)
    spew.Println("pre+mid:", isSameTree(root, tmp))
    tmp = NewTreeNode(mid, post, 2, false)
    spew.Println("mid+post:", isSameTree(root, tmp))
}

/*测试递归解法*/
func testRecursive(root *TreeNode) {
    spew.Println("----------- in testRecursive")
    defer spew.Println("----------- out testRecursive")
    b, _ := json.Marshal(treeOrder(root, 1))
    pre := string(b)
    b, _ = json.Marshal(treeOrder(root, 2))
    mid := string(b)
    b, _ = json.Marshal(treeOrder(root, 3))
    post := string(b)
    b, _ = json.Marshal(treeOrder(root, 4))
    level := string(b)
    spew.Println("pre:", pre)
    spew.Println("mid:", mid)
    spew.Println("post:", post)
    spew.Println("level:", level)
    tmp := NewTreeNode(pre, mid, 1, true)
    spew.Println("pre+mid:", isSameTree(root, tmp))
    tmp = NewTreeNode(mid, post, 2, true)
    spew.Println("mid+post:", isSameTree(root, tmp))

}

type (
    TreeNode struct {
        Val   int
        Left  *TreeNode
        Right *TreeNode
    }
    ListNode struct {
        Val  int
        Next *ListNode
    }
)

func arrayFromString(val string) ([]int, int) {
    var res []int /* [1,2,3,null,4,5],null=0 */
    if json.Unmarshal([]byte(val), &res) != nil {
        return nil, 0
    }
    return res, len(res)
}

/*根据输入得到一个链表*/
func NewListNode(val string) *ListNode {
    arr, la := arrayFromString(val)
    if la == 0 {
        return nil
    }
    head := &ListNode{Val: arr[0]}
    p := head
    for i := 1; i < la; i++ {
        p.Next = &ListNode{Val: arr[i]}
        p = p.Next
    }
    return head
}

/*根据2个序列还原二叉树*/
func NewTreeNode(s0, s1 string, mode int, isRecursive bool) *TreeNode {
    a0, l0 := arrayFromString(s0)
    a1, l1 := arrayFromString(s1)
    if l0 != l1 || l0 == 0 {
        return nil
    }
    switch mode {
    case 1: /*先序+中序*/
        if isRecursive { /*递归*/
            return preOrMidRecursive(a0, a1, 0, l0, 0, l0)
        }
        return preOrMidTraverse(a0, a1, l0)
    case 2: /*中序+后序*/
        if isRecursive { /*递归*/
            return midOrPostRecursive(a0, a1, 0, l0, 0, l0)
        }
        return midOrPostTraverse(a0, a1, l0)
    }
    return nil
}

/*中序+后序还原二叉树,非递归*/
func midOrPostTraverse(mid []int, post []int, length int) *TreeNode {
    var (
        root      = &TreeNode{Val: post[length-1]}
        isVisited = make([]bool, length)
        rootIndex = intIndex(mid, post[length-1])
        i, cur    = length - 2, root
        st        = NewStackQueue(nil, nil)
    )