package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
	result := [][]int{}
	if root == nil {
		return result
	}
	zigzagLevelOrderHelper(root, 0, &result)
	return result
}

func zigzagLevelOrderHelper(root *TreeNode, level int, result *[][]int) {
	if root.Left != nil {
		zigzagLevelOrderHelper(root.Left, level+1, result)
	}
	for len(*result) <= level {
		*result = append(*result, []int{})
	}
	if level%2 == 0 {
		(*result)[level] = append((*result)[level], root.Val)
	} else {
		(*result)[level] = append([]int{root.Val}, (*result)[level]...)
	}
	if root.Right != nil {
		zigzagLevelOrderHelper(root.Right, level+1, result)
	}
}

// func main() {
// 	//        1
// 	//       / \
// 	//      2   3
// 	//     / \
// 	//    4   5
// 	n5 := TreeNode{5, nil, nil}
// 	n4 := TreeNode{4, nil, nil}
// 	n3 := TreeNode{3, nil, nil}
// 	n2 := TreeNode{2, &n4, &n5}
// 	n1 := TreeNode{1, &n2, &n3}
// 	fmt.Println(zigzagLevelOrder(&n1))
// }