算法题--将升序排列的链表转化为一棵二叉搜索树

image.png

0. 链接

题目链接

1. 题目

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

2. 思路1: 先转化为数组, 再按照取中心点作为根节点的方法递归构造

时间复杂度O(N)
空间复杂度O(N)

3. 代码

# Convert the given linked list to an array
def mapListToValues(self, head):
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    return vals    

def sortedListToBST(self, head):
    """
    :type head: ListNode
    :rtype: TreeNode
    """

    # Form an array out of the given linked list and then
    # use the array to form the BST.
    values = self.mapListToValues(head)

    # l and r represent the start and end of the given array
    def convertListToBST(l, r):

        # Invalid case
        if l > r:
            return None

        # Middle element forms the root.
        mid = (l + r) // 2
        node = TreeNode(values[mid])

        # Base case for when there is only one element left in the array
        if l == r:
            return node

        # Recursively form BST on the two halves
        node.left = convertListToBST(l, mid - 1)
        node.right = convertListToBST(mid + 1, r)
        return node
    return convertListToBST(0, len(values) - 1)

def print_tree(root):
    array = list()

    def preorder_traverse(node):
        array.append(node.val)
        if node.left is not None:
            preorder_traverse(node.left)
        else:
            array.append(None)
        if node.right is not None:
            preorder_traverse(node.right)
        else:
            array.append(None)

    if root is not None:
        preorder_traverse(root)
    print(array)


solution = Solution()
head = node = ListNode(-10)
node.next = ListNode(-3)
node = node.next
node.next = ListNode(0)
node = node.next
node.next = ListNode(5)
node = node.next
node.next = ListNode(9)
node = node.next

print_tree(solution.sortedListToBST(head))

输出结果

[0, -10, None, -3, None, None, 5, None, 9, None, None]

4. 结果

image.png

5. 思路2: 先算出元素数量+再使用递归

• 先遍历一次链表, 计算出元素数量size
• 再按照中序遍历的思路, 进行递归调用

def 处理一棵树(l, r):
    处理左子树[l, mid - 1]
    从链表中取出一个值作为当前根节点
    处理右子树[mid + 1, l]

可以看出, 按照这样的步骤, 左下角的那个节点, 首次取出链表头部元素, 然后其父节点再取第二个元素, 其右兄弟节点取出第三个元素, 这样一个子树构建完成; 按照这样的构建思路, 逐渐从左下角到中间到右下角，逐渐构造完一棵树

这个递归方法一共被调用logN次, 意味着计算过程中分配的空间复杂度为O(logN)

6. 代码

class Solution1:
    def sortedListToBST(self, head: ListNode) -> TreeNode:

        def convert(l, r):
            nonlocal head

            if l > r:
                return None
            mid = l + (r - l) // 2
            left = convert(l, mid - 1)
            node = TreeNode(head.val)
            head = head.next
            node.left = left
            node.right = convert(mid + 1, r)

            return node

        size = 0
        each_node = head
        while each_node is not None:
            size += 1
            each_node = each_node.next

        return convert(0, size - 1)


def print_tree(root):
    array = list()

    def preorder_traverse(node):
        array.append(node.val)
        if node.left is not None:
            preorder_traverse(node.left)
        else:
            array.append(None)
        if node.right is not None:
            preorder_traverse(node.right)
        else:
            array.append(None)

    if root is not None:
        preorder_traverse(root)
    print(array)


solution = Solution1()
head = node = ListNode(-10)
node.next = ListNode(-3)
node = node.next
node.next = ListNode(0)
node = node.next
node.next = ListNode(5)
node = node.next
node.next = ListNode(9)
node = node.next

print_tree(solution.sortedListToBST(head))

输出结果为

[0, -10, None, -3, None, None, 5, None, 9, None, None]

7. 结果

image.png