【每日一题】- 2019-08-28 - 109. 有序链表转换二叉搜索树-推荐 about leetcode HOT 6 CLOSED

/**
 * 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 sortedListToBST(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	}
	lenList := 0
	cur := head

	for cur != nil {
		cur = cur.Next
		lenList++
	}

	return binarySearch(&head, 0, lenList-1)

}

func binarySearch(head **ListNode, start int, end int) *TreeNode {
	if start > end {
		return nil //
	}

	mid := (start + end) / 2
	left := binarySearch(head, start, mid-1)
	root := &TreeNode{(*head).Val, nil, nil}
	root.Left = left
	*head = (*head).Next

	//order must leftSubTree, head ,rightSubTree
	right := binarySearch(head, mid+1, end)
	root.Right = right

	return root
}