/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func largestValues(root *TreeNode) (res []int) {
	preorder(root, 0, &res) // DFS
	return
}

func preorder(root *TreeNode, depth int, res *[]int) {
	if root == nil {
		return
	}
	if depth == len(*res) {
		*res = append(*res, root.Val)
	} else if (*res)[depth] < root.Val {
		(*res)[depth] = root.Val
	}
	preorder(root.Left, depth+1, res)
	preorder(root.Right, depth+1, res)
}

func largestValuesBFS(root *TreeNode) (res []int) {
	if root == nil {
		return
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	size := 1
	for size != 0 {
		max, l := queue[0].Val, size
		for i := 0; i < l; i++ {
			node := queue[0]
			queue = queue[1:]
			size--
			if max < node.Val {
				max = node.Val
			}
			if node.Left != nil {
				queue = append(queue, node.Left)
				size++
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
				size++
			}
		}
		res = append(res, max)
	}
	return
}