# 题目

给定的有序链表： [-10, -3, 0, 5, 9],

0
/ \
-3   9
/   /
-10  5


# 解题思路

## 二叉树的性质

2 作为根节点，[ 1 ] 作为左子树，[ 3…n ] 的所有可能作为右子树。

3 作为根节点，[ 1 2 ] 的所有可能作为左子树，[ 4 … n ] 的所有可能作为右子树，然后左子树和右子树两两组合。

4 作为根节点，[ 1 2 3 ] 的所有可能作为左子树，[ 5 … n ] 的所有可能作为右子树，然后左子树和右子树两两组合。

n 作为根节点，[ 1… n ] 的所有可能作为左子树，[ ] 作为右子树。

## 高度平衡

int left = total / 2;

int right = total - left;


## 实现

public TreeNode sortedListToBST(ListNode head) {
if(list.size() <= 0) {
return null;
}
return generateTree(list, 0, list.size()-1);
}

private TreeNode generateTree(List<Integer> list, int start, int end) {
//此时没有数字，将 null 加入结果中
if(start > end) {
return null;
}
// root 节点
// 1 2 3 4 5
int rootIndex = start + (end - start) / 2;
int rootVal = list.get(rootIndex);
TreeNode treeNode = new TreeNode(rootVal);
// left
treeNode.left = generateTree(list, start, rootIndex-1);
// right
treeNode.right = generateTree(list, rootIndex+1, end);
return treeNode;
}

List<Integer> list = new ArrayList<>();
}
return list;
}


Runtime: 1 ms, faster than 43.98% of Java online submissions for Convert Sorted List to Binary Search Tree.
Memory Usage: 40.4 MB, less than 24.39% of Java online submissions for Convert Sorted List to Binary Search Tree.


# 优化方式-分治

## java 实现

public TreeNode sortedListToBST(ListNode head) {
}

public TreeNode buildTree(ListNode left, ListNode right) {
if (left == right) {
return null;
}
ListNode mid = getMedian(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(left, mid);
root.right = buildTree(mid.next, right);
return root;
}

public ListNode getMedian(ListNode left, ListNode right) {
ListNode fast = left;
ListNode slow = left;
while (fast != right && fast.next != right) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Convert Sorted List to Binary Search Tree.
Memory Usage: 39.9 MB, less than 61.25% of Java online submissions for Convert Sorted List to Binary Search Tree.


# 参考资料

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