package main

// TreeNode ...
// type TreeNode struct {
// 	Val   int
// 	Left  *TreeNode
// 	Right *TreeNode
// }

func reverseArr(arr *[][]int) {
	for i, j := 0, len(*arr)-1; i < j; i, j = i+1, j-1 {
		(*arr)[i], (*arr)[j] = (*arr)[j], (*arr)[i]
	}
}

func levelOrderBottomIter(curr *TreeNode, depth int, arr *[][]int) {
	if curr == nil {
		return
	}
	if curr.Left != nil {
		levelOrderBottomIter(curr.Left, depth+1, arr)
	}
	if curr.Right != nil {
		levelOrderBottomIter(curr.Right, depth+1, arr)
	}
	for len(*arr) < depth+1 {
		layer := make([]int, 0)
		*arr = append(*arr, layer)
	}
	(*arr)[depth] = append((*arr)[depth], curr.Val)
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
	arr := make([][]int, 0)
	levelOrderBottomIter(root, 0, &arr)
	reverseArr(&arr)
	return arr
}

// func main() {
// 	/**
// 	 * t1:  5
// 	 *     / \
// 	 *    1   4
// 	 *       / \
// 	 *      2   3
// 	 */
// 	t1l := TreeNode{1, nil, nil}
// 	t1rl := TreeNode{2, nil, nil}
// 	t1rr := TreeNode{3, nil, nil}
// 	t1r := TreeNode{4, &t1rl, &t1rr}
// 	t1 := &TreeNode{5, &t1l, &t1r}
// 	t2 := &TreeNode{9, nil, nil}
// 	fmt.Println(levelOrderBottom(t1))
// 	fmt.Println(levelOrderBottom(t2))
// }