/*ConvertListToBST.java

Convert Sorted List to Balanced BST

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

Example

2

1->2->3 => / \

1 3

Tags Recursion Linked List

*/

/**

* Definition for ListNode.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int val) {

* this.val = val;

* this.next = null;

* }

* }

* Definition of TreeNode:

* public class TreeNode {

* public int val;

* public TreeNode left, right;

* public TreeNode(int val) {

* this.val = val;

* this.left = this.right = null;

* }

* }

*/

public class ConvertListToBST {

/**

* @param head: The first node of linked list.

* @return: a tree node

*/

public TreeNode sortedListToBST(ListNode head) {

// write your code here

}

}