requirements

Given a single linked list whose elements are sorted in ascending order, convert it into a highly balanced binary search tree.

In this case, a highly balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree is less than 1.

Example:

Given an ordered list: [-10, -3, 0, 5, 9], a possible answer is [0, -3, 9, -10, NULL, 5], which can represent the following highly balanced binary search tree: 0 / \ -3 9 / / -10 5Copy the code

The core code

# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        l = list(a)while head:
            l.append(head.val)
            head = head.next
        def sortedArrayToBST(nums) :
            if not nums:
                return None
            def dfs(start,end) :
                if end < start:
                    return
                mid = (end + start) //2
                root = TreeNode(nums[mid])
                root.left = dfs(start,mid-1)
                root.right = dfs(mid+1,end)
                return root
            return dfs(0.len(nums)-1)
        return sortedArrayToBST(l)
Copy the code

Another solution

# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        slow ,fast = head,head
        pre = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None
        part1 = head
        part2 = slow.next
        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(part1)
        root.right = self.sortedListToBST(part2)
        return root
Copy the code

The first solution is the same as that in the previous problem, leetcode_108 restores a balanced search binary tree by using an ascending list. We can first change the ordered list to an ordered array, and then use the code in the previous problem to complete the construction. The second solution: in this solution, we use the way of fast and slow Pointers to find the median, and will get the left and right two new linked lists, we can use the recursive way, complete the left and right subtree construction.