package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedListToBSTOld(head *ListNode) *TreeNode {
	list := make([]int, 0)
	curr := head
	for curr != nil {
		list = append(list, curr.Val)
		curr = curr.Next
	}
	return sortedArrayToBST(list)
}

func sortedArrayToBST(num []int) *TreeNode {
	length := len(num)
	if length == 0 {
		return nil
	} else if length == 1 {
		return &TreeNode{num[0], nil, nil}
	}
	mid := length / 2
	root := TreeNode{num[mid], nil, nil}
	root.Left = sortedArrayToBST(num[:mid])
	root.Right = sortedArrayToBST(num[mid+1:])
	return &root
}

func sortedListToBST(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	} else if head.Next == nil {
		return &TreeNode{head.Val, nil, nil}
	}
	return listToBSTHelper(head, nil)
}

func listToBSTHelper(head, tail *ListNode) *TreeNode {
	if head == tail {
		return nil
	}
	slow := head
	fast := head
	for fast != tail && fast.Next != tail {
		slow = slow.Next
		fast = fast.Next.Next
	}
	root := TreeNode{slow.Val, nil, nil}
	root.Left = listToBSTHelper(head, slow)
	root.Right = listToBSTHelper(slow.Next, tail)
	return &root
}

// func main() {
// 	printTree(sortedListToBST((toLinkedList(
// 		[]int{-10, -3, 0, 5, 9}))))
// 	printTree(sortedListToBST((toLinkedList(
// 		[]int{}))))
// 	printTree(sortedListToBST((toLinkedList(
// 		[]int{1, 2}))))
// }