0109-convert-sorted-list-to-binary-search-tree.adoc

109. 有序链表转换二叉搜索树

LeetCode - 109. 有序链表转换二叉搜索树

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为平衡 二叉搜索树。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

提示:

• head 中的节点数在 [0, 2 * 104] 范围内

• -105 <= Node.val <= 105

思路分析

这道题跟 108. Convert Sorted Array to Binary Search Tree 类似。可以转化成数组（或链表）进行求解。这属于空间换时间的解法。

另外一种解法，就是使用快慢指针，找到中间节点，然后再构造二叉树。

还有一种解法：利用分治+中序遍历，先逐步构建左树，然后构建根节点，最后构建右树。

一刷

link:{sourcedir}/_0109_ConvertSortedListToBinarySearchTree.java[role=include]

二刷

link:{sourcedir}/_0109_ConvertSortedListToBinarySearchTree_2.java[role=include]

二刷（优化）

link:{sourcedir}/_0109_ConvertSortedListToBinarySearchTree_21.java[role=include]

参考资料

1. 109. 有序链表转换二叉搜索树 - 力扣（LeetCode）