# 109.Convert-Sorted-List-to-Binary-Search-Tree

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

https://www.lintcode.com/problem/convert-sorted-list-to-binary-search-tree/description

https://www.jiuzhang.com/solutions/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.

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``````

## ไปฃ็ 

### Approach #1

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
if (head == null) return null;

}

if (head == null) return null;

// cut the list in two
ListNode pre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;

// binary
TreeNode root = new TreeNode(slow.val);
TreeNode R = helper(slow.next);
root.left = L;
root.right = R;

return root;
}

}``````

### Approach solution 2:

``````public class Solution {
int len = 0;
len++;
}
return len;
}

int len = getListLength(current);
}

public TreeNode helper(int len) {
if (len <= 0) return null;

TreeNode left = helper(len / 2);
TreeNode right = helper(len - 1 - len / 2);

root.left = left;
root.right = right;

return root;
}``````

### Approach #3 Recursion + Conversion to Array

``````class Solution {

private List<Integer> values;

public Solution() {
this.values = new ArrayList<Integer>();
}

}
}

private TreeNode convertListToBST(int left, int right) {
// Invalid case
if (left > right) {
return null;
}

// Middle element forms the root.
int mid = (left + right) / 2;
TreeNode node = new TreeNode(this.values.get(mid));

// Base case for when there is only one element left in the array
if (left == right) {
return node;
}

// Recursively form BST on the two halves
node.left = convertListToBST(left, mid - 1);
node.right = convertListToBST(mid + 1, right);
return node;
}