package binarytreezigzaglevelordertraversal

import . "gitee.com/dllearn/geektime-algorithm-learn/structures"

// 103. 二叉树的锯齿形层序遍历
// https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

func zigzagLevelOrder(root *TreeNode) [][]int {

	if root == nil {
		return nil
	}
	res := make([][]int, 0)
	dfs(root, 1, &res)
	return res
}

func dfs(node *TreeNode, level int, res *[][]int) {
	if node == nil {
		return
	}
	if len(*res) < level {
		*res = append(*res, []int{node.Val})
	} else {
		if level%2 == 0 { // 加到 head
			(*res)[level-1] = append([]int{node.Val}, (*res)[level-1]...)
		} else {
			(*res)[level-1] = append((*res)[level-1], node.Val)
		}
	}

	dfs(node.Left, level+1, res)
	dfs(node.Right, level+1, res)

	return

}