二叉树的各种遍历

中序遍历：左节点（左子树），中间节点，右节点（右子树）
前序遍历：中间节点，左节点（左子树），右节点（右子树）
后序遍历：左节点（左子树），右节点（右子树），中间节点
层序遍历：从根节点到最底层节点，每一层遍历

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

    // 当队列中数据为空的时候程序退出
    for stackData.Len() > 0 {

        // 新队列
        stackData1 := list.New()
        var tmpRet []int
        // 遍历当前层数据
        for stackData.Len() > 0 {
            currentNode := stackData.Front()
            stackData.Remove(currentNode)
            current := currentNode.Value.(*TreeNode)

            // 当前数据保存
            tmpRet = append(tmpRet, current.Val)

            // 左，右节点依次入队列处理
            if current.Left != nil {
                stackData1.PushBack(current.Left)
            }

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

        }

        res = append(res, tmpRet)
        // 交换新旧队列位置
        stackData = stackData1

        // 层数加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
}

/*
    后序遍历：
        先从左到右 ,先叶子后节点的方式遍历访问左右子树，最后访问根节点
*/
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()

    // 栈不为空或者根节点部位空的时候处理
    for root != nil || stack.Len() > 0 {

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

        // 取出一个数据处理
        tempNode := stack.Back()
        stack.Remove(tempNode)
        root = tempNode.Value.(*TreeNode)

        // 右节点没有处理过或者已经处理过右节点，则处理当前节点
        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root // 记录下当前处理节点
            root = nil  // 标记该节点已经处理完毕
        } else {
            // 右节点未处理过则需要入栈继续处理
            stack.PushBack(root)
            root = root.Right
        }
    }

    return res
}

/*
    前序遍历的定义：
        先访问根节点，然后前序遍历左子树，再前序遍历右子树

    递归方式
*/
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
}

/*
    中序遍历的定义：
    先遍历根节点的左子树，然后访问根节点的，最后遍历右子树

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

    res := make([]int, 0)

    if root == nil {
        return res
    }

    stackData := list.New()

    // 需要一个栈来处理
    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)
    }

    // 处理左边的数据
    left = middle(root.Left)

    right = middle(root.Right)

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