题目描述

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

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。