二叉树的锯齿形层序遍历（Go）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res [][]int

func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	res = [][]int{}
	DSF(root, 0)

    for k, v := range res {
        if k % 2 != 0 {
            for i, n := 0, len(v); i < n / 2; i ++ {
                v[i], v[n-1-i] = v[n-1-i], v[i]
            }
        }
    }
	return res
}

func DSF(root * TreeNode, level int) {
	if root == nil {
		return
	}

	if level == len(res) {
		res = append(res, []int{})
	}

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

	DSF(root.Left, level + 1)
	DSF(root.Right, level + 1)

}