0109. Convert Sorted List to Binary Search Tree

# 109. Convert Sorted List to Binary Search Tree#

## 题目 #

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5

## 代码 #

package leetcode

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

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

return nil
}
return &TreeNode{Val: head.Val, Left: nil, Right: nil}
}
if middleNode == nil {
return nil
}
if preNode != nil {
preNode.Next = nil
}
}
return &TreeNode{Val: middleNode.Val, Left: sortedListToBST(head), Right: sortedListToBST(middleNode.Next)}
}

func middleNodeAndPreNode(head *ListNode) (middle *ListNode, pre *ListNode) {
}