package main

import (
	"strconv"
)

// Integer ...
type Integer *int

func newInt(n int) Integer {
	i := new(int)
	*i = n
	return i
}

// Point ...
type Point struct {
	X int
	Y int
}

// ListNode ...
type ListNode struct {
	Val  int
	Next *ListNode
}

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

// Interval ...
type Interval struct {
	Start int
	End   int
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func maxInt(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func minInts(vals ...int) (min int) {
	min = vals[0]
	for i := 1; i < len(vals); i++ {
		if vals[i] < min {
			min = vals[i]
		}
	}
	return
}

func toLinkedList(num []int) *ListNode {
	length := len(num)
	if length == 0 {
		return nil
	}
	head := ListNode{num[0], nil}
	curr := &head
	for i := 1; i < length; i++ {
		curr.Next = &ListNode{num[i], nil}
		curr = curr.Next
	}
	return &head
}

func printList(head *ListNode) {
	curr := head
	for curr != nil {
		print(strconv.FormatInt(int64(curr.Val), 10), " ")
		curr = curr.Next
	}
	println()
}

func sortedToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	mid := len(nums) / 2
	root := TreeNode{nums[mid], nil, nil}
	// only one element in nums, return TreeNode{ele, nil, nil}
	if mid == 0 {
		return &root
	}
	root.Left = sortedToBST(nums[:mid])
	root.Right = sortedToBST(nums[mid+1:])
	return &root
}

func toBinaryTree(nums ...Integer) *TreeNode {
	if nums[0] == nil {
		return nil
	}
	root := &TreeNode{*nums[0], nil, nil}
	upperLevel := []*TreeNode{root}
	thisLevel := []*TreeNode{}
	var curr *TreeNode
	for i := 1; i < len(nums); i++ {
		if i%2 == 1 { // Left child
			curr = upperLevel[0]
			upperLevel = upperLevel[1:]
			if nums[i] != nil {
				curr.Left = &TreeNode{*nums[i], nil, nil}
				thisLevel = append(thisLevel, curr.Left)
			}
		} else { // Right child
			if nums[i] != nil {
				curr.Right = &TreeNode{*nums[i], nil, nil}
				thisLevel = append(thisLevel, curr.Right)
			}
			if len(upperLevel) == 0 {
				upperLevel = thisLevel
				thisLevel = []*TreeNode{}
			}
		}
	}
	return root
}

func printTree(root *TreeNode) { // Level order traversal
	if root == nil {
		println("nil")
		return
	}
	queue := make([]*TreeNode, 0) // Important!
	queue = append(queue, root)
	for len(queue) != 0 {
		curr := queue[0]
		queue = queue[1:] // Dequeue
		if curr == nil {
			print("nil ")
			continue
		}
		print(curr.Val, " ")
		queue = append(queue, curr.Left)
		queue = append(queue, curr.Right)
	}
	println()
}

func printBoard(board [][]byte) {
	for _, row := range board {
		for _, grid := range row {
			print(string(grid), " ")
		}
		println()
	}
}