package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
	view := make([]int, 0)
	if root == nil {
		return view
	}
	type Node struct {
		Ptr   *TreeNode
		Level int
	}
	viewed := make(map[int]bool)
	queue := make([]Node, 0)
	curr := root
	queue = append(queue, Node{curr, 0})
	for len(queue) != 0 {
		curr = queue[0].Ptr
		level := queue[0].Level
		queue = queue[1:] // Pop
		if !viewed[level] {
			view = append(view, curr.Val)
			viewed[level] = true
		}
		if curr.Right != nil {
			queue = append(queue, Node{curr.Right, level + 1})
		}
		if curr.Left != nil {
			queue = append(queue, Node{curr.Left, level + 1})
		}
	}
	return view
}

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