二叉树之字形排序

内容纲要

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解题思路

设置一个栈，对整个二叉树进行层序遍历，奇数层直接打印，偶数层入栈，然后出栈打印，依次类推。。。

递归三部曲

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

go代码

//二叉树节点
type treeNode struct {
    value int
    left  *treeNode
    right *treeNode
}
//用于对二叉树层序遍历使用
var l list.List

func asf(root *treeNode) {
    //判断是否为空
    if root == nil {
        return
    }
    //标记当前层数，判断是奇数还是偶数
    n := 1
    l.PushBack(root)
    for l.Len() > 0 {
        length := l.Len()
        var tmp list.List
        for i := 0; i < length; i++ {
            node := l.Remove(l.Front()).(*treeNode)
            if n%2 == 1 {
                //奇数层直接打印
                fmt.Print(node.value, " ")
            } else {
                //偶数层放入栈中
                tmp.PushBack(node.value)
            }
            if node.left != nil {
                l.PushBack(node.left)
            }
            if node.right != nil {
                l.PushBack(node.right)
            }
        }
        //对偶数层进行出栈打印操作
        for tmp.Len() > 0 {
            fmt.Print(tmp.Remove(tmp.Back()), " ")
        }
        //打印换行
        fmt.Println()
        n++
    }
}