中序遍歷：左節(jié)點(diǎn)（左子樹），中間節(jié)點(diǎn)奢米，右節(jié)點(diǎn)（右子樹）
前序遍歷：中間節(jié)點(diǎn)掏导，左節(jié)點(diǎn)（左子樹）享怀，右節(jié)點(diǎn)（右子樹）
后序遍歷：左節(jié)點(diǎn)（左子樹），右節(jié)點(diǎn)（右子樹）趟咆，中間節(jié)點(diǎn)
層序遍歷：從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)添瓷，每一層遍歷

func Start() {

    root := &TreeNode{
        Val: 1,
        Left: &TreeNode{
            Val: 2,
            Left: &TreeNode{
                Val: 4,
            },
            Right: &TreeNode{
                Val: 5,
            },
        },
        Right: &TreeNode{
            Val: 3,
            Left: &TreeNode{
                Val: 6,
            },
            Right: &TreeNode{
                Val: 7,
            },
        },
    }

    fmt.Println(layer(root))
    fmt.Println(layerLoop(root))
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 層序遍歷的迭代
func layerLoop(root *TreeNode) [][]int {
    var res [][]int

    stackData := list.New()
    index := 0

    if root != nil {
        stackData.PushBack(root)
    }

    // 當(dāng)隊(duì)列中數(shù)據(jù)為空的時(shí)候程序退出
    for stackData.Len() > 0 {

        // 新隊(duì)列
        stackData1 := list.New()
        var tmpRet []int
        // 遍歷當(dāng)前層數(shù)據(jù)
        for stackData.Len() > 0 {
            currentNode := stackData.Front()
            stackData.Remove(currentNode)
            current := currentNode.Value.(*TreeNode)

            // 當(dāng)前數(shù)據(jù)保存
            tmpRet = append(tmpRet, current.Val)

            // 左，右節(jié)點(diǎn)依次入隊(duì)列處理
            if current.Left != nil {
                stackData1.PushBack(current.Left)
            }

            if current.Right != nil {
                stackData1.PushBack(current.Right)
            }

        }

        res = append(res, tmpRet)
        // 交換新舊隊(duì)列位置
        stackData = stackData1

        // 層數(shù)加1
        index++

    }

    return res
}

// 層序遍歷的遞歸
func layer(root *TreeNode) [][]int {
    res := make([][]int, 0)
    var layerDeliver func(root *TreeNode, layer int)

    layerDeliver = func(root *TreeNode, layer int) {

        if root == nil {
            return
        }

        if len(res) == layer {
            res = append(res, make([]int, 0))
        }

        res[layer] = append(res[layer], root.Val)

        layer++
        layerDeliver(root.Left, layer)
        layerDeliver(root.Right, layer)
    }

    layerDeliver(root, 0)
    return res
}

/*
    后序遍歷：
        先從左到右 ,先葉子后節(jié)點(diǎn)的方式遍歷訪問左右子樹值纱，最后訪問根節(jié)點(diǎn)
*/
func after(root *TreeNode) []int {
    res := make([]int, 0)

    if root == nil {
        return res
    }

    left := after(root.Left)
    right := after(root.Right)

    return append(append(left, right...), root.Val)
}

func afterLoop(root *TreeNode) []int {
    var res []int
    var prev *TreeNode

    // 獲取棧處理
    stack := list.New()

    // 棧不為空或者根節(jié)點(diǎn)部位空的時(shí)候處理
    for root != nil || stack.Len() > 0 {

        // 一路往左走到底
        for root != nil {
            stack.PushBack(root)
            root = root.Left
        }

        // 取出一個(gè)數(shù)據(jù)處理
        tempNode := stack.Back()
        stack.Remove(tempNode)
        root = tempNode.Value.(*TreeNode)

        // 右節(jié)點(diǎn)沒有處理過或者已經(jīng)處理過右節(jié)點(diǎn)鳞贷，則處理當(dāng)前節(jié)點(diǎn)
        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root // 記錄下當(dāng)前處理節(jié)點(diǎn)
            root = nil  // 標(biāo)記該節(jié)點(diǎn)已經(jīng)處理完畢
        } else {
            // 右節(jié)點(diǎn)未處理過則需要入棧繼續(xù)處理
            stack.PushBack(root)
            root = root.Right
        }
    }

    return res
}

/*
    前序遍歷的定義：
        先訪問根節(jié)點(diǎn)，然后前序遍歷左子樹虐唠，再前序遍歷右子樹

    遞歸方式
*/
func before(root *TreeNode) []int {
    res := make([]int, 0)
    var left, right []int

    if root == nil {
        return res
    }

    res = append(res, root.Val)

    left = before(root.Left)

    right = before(root.Right)

    return append(append([]int{root.Val}, left...), right...)
}

func beforeLoop(root *TreeNode) []int {
    res := make([]int, 0)

    stackData := list.New()

    for stackData.Len() > 0 || root != nil {

        if root != nil {
            res = append(res, root.Val)
            stackData.PushBack(root)
            root = root.Left
        } else {
            // 左子樹遍歷完畢再遍歷 右子樹
            node := stackData.Back()
            stackData.Remove(node)
            nodeData := node.Value.(*TreeNode)
            root = nodeData.Right
        }

    }

    return res
}

/*
    中序遍歷的定義：
    先遍歷根節(jié)點(diǎn)的左子樹搀愧，然后訪問根節(jié)點(diǎn)的，最后遍歷右子樹

    中序遍歷迭代
*/
func middleLoop(root *TreeNode) []int {

    res := make([]int, 0)

    if root == nil {
        return res
    }

    stackData := list.New()

    // 需要一個(gè)棧來處理
    for stackData.Len() > 0 || root != nil {

        if root != nil {
            stackData.PushBack(root)
            root = root.Left
        } else {
            tmp := stackData.Back()
            stackData.Remove(tmp)
            tmpNode := tmp.Value.(*TreeNode)

            res = append(res, tmpNode.Val)
            root = tmpNode.Right
        }
    }

    return res
}

/**
 *  中序遍歷 - 遞歸
 */
func middle(root *TreeNode) []int {

    var left, right []int

    if root == nil {
        return make([]int, 0)
    }

    // 處理左邊的數(shù)據(jù)
    left = middle(root.Left)

    right = middle(root.Right)

    res := append(append(left, root.Val), right...)
    return res
}