题目描述
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
# 首先转成数组,就可以按照索引来快速获取中间值
arr = []
result = []
while head is not None:
arr.append(head.val)
head = head.next
def sortedArryToBST(arr):
if len(arr)==0:
return None
if len(arr) == 1:
return TreeNode(arr[0])
mid = (len(arr))//2
root = TreeNode(arr[mid])
root.left = sortedArryToBST(arr[:mid])
root.right = sortedArryToBST(arr[mid+1:])
return root
return sortedArryToBST(arr)
图片.png
还可以使用快慢指针来获得中间值
d072de5dd5b0ff86df59ff948b5f1b2.jpg
上述两种方式都是寻找方法获得中节点 用中间节点构建root，导致我们每次构建树节点得时候都要寻找中间节点
能不能不寻找中间节点，而是令建立节点的顺序 匹配 链表元素顺序？这样每次建立节点时，只需要获取链表下一个元素即可。方法如下：
- 使用递归模拟中序遍历过程，建立节点的顺序即与链表元素顺序一一对应，bottom-up建立树，最终返回根节点。递归调用得最底层一个节点得左儿子是空，右儿子也是空，只有父节点是链表得head.val。
- 递归前需要统计链表长度n，整体算法复杂度O(N)。
作者：jyd
链接：https://leetcode-cn.com/problems/two-sum/solution/convert-sorted-list-to-binary-search-tree-di-ding-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution:
def __init__(self):
self.head = None
def sortedListToBST(self, head: ListNode) -> TreeNode:
n, self.head = 0, head
while head:
head = head.next
n += 1
return self.to_bst(0, n - 1)
def to_bst(self, left, right):
if left > right: return
m = (left + right) // 2
left_child = self.to_bst(left, m - 1)
father = TreeNode(self.head.val)
self.head = self.head.next
father.left = left_child
father.right = self.to_bst(m + 1, right)
return father
作者：jyd
链接：https://leetcode-cn.com/problems/two-sum/solution/convert-sorted-list-to-binary-search-tree-di-ding-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
