Sui Xin's Blog

[LeetCode]109. 有序链表转换二叉搜索树（Convert Sorted List to Binary Search Tree）

Posted on In Disqus:

题目描述

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

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

0
/ \
-3 9
/ /
-10 5

解题思路

  1. 解法一：快慢指针。使用快慢指针找到链表的中间节点，即为二叉搜索树的根节点，然后递归链表左半部分和右半部分；
  2. 解法二：模拟中序遍历。二叉搜索树的中序遍历结果刚好为单调递增的数组。首先确定链表的长度，然后模拟中序遍历时先找到中间的元素，递归左半边，当左半边完成时，head 指针刚好指向中间节点，将中间节点改为树节点，然后再递归右半边即可。

代码

Python 3.6

解法一：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 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:
        if head is None:
            return None
        if head.next is None:
            return TreeNode(head.val)
        slow = ListNode(-1)
        slow.next = head
        fast = head
        while fast is not None:
            last = slow
            slow = slow.next
            fast = fast.next.next if fast.next is not None else None
        last.next = None
        right = slow.next
        slow.next = None
        root = TreeNode(slow.val)
        if slow is not head:
            root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(right)
        return root

执行用时 : 160 ms
内存消耗 : 17.4 MB

解法二：模拟中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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:
        length = 0
        cur = head
        while cur is not None:
            length += 1
            cur = cur.next
        
        def convert(l, r):
            if l > r:
                return None
            
            nonlocal head
            mid = (l + r) // 2
            left = convert(l, mid - 1)
            node = TreeNode(head.val)
            head = head.next
            node.left = left
            node.right = convert(mid + 1, r)
            return node
        
        return convert(0, length - 1)

执行用时 : 200 ms
内存消耗 : 20.3 MB

参考

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-by-/

Related Posts