[109][中等][DFS][双指针] 有序链表转换二叉搜索树

题目描述

109. 有序链表转换二叉搜索树

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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

解题思路

转成数组

一个直接的思路就是先将整个列表过一遍, 将每个节点的值取出来组成一个递增的数组, 这样问题就转换成了 108. 将有序数组转换为二叉搜索树. 实际上这种方法的效率也是比较高的. 解法如下:

# 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:
        nums = []
        current = head
        while current is not None:
            nums.append(current.val)
            current = current.next

        n = len(nums)

        def get_root(l, r):
            if l > r:
                return None

            mid = (l + r) // 2
            root = TreeNode(nums[mid])
            root.left = get_root(l, mid - 1)
            root.right = get_root(mid + 1, r)
            return root
        return get_root(0, n - 1)

快慢指针(双指针)

如果不转成数组, 只是用链表的方法, 我们仍然要找到中间节点. 常常使用双指针, 一快一慢, 快慢指针配合找到中间节点. 分别定义为slow_ptr和fast_ptr, slow_ptr每次移动一个结点, fast_ptr每次移动两个结点, 这样当fast_ptr移动到链表的截尾时, slow_ptr正好访问到中间节点, 无论链表的长度奇偶.

仍然使用递归方法, 找到中间节点后, 将中间节点的前后断开, 然后前后子链再递归地使用同样的方法找到中间节点. 为了找到中间节点, 即slow_ptr, 再使用一个指针prev_ptr, 记录slow_ptr前一个元素.

具体内容参考:

有序链表转换二叉搜索树

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def get_root(pointer):
            if pointer is None:
                return None
            if pointer.next is None:
                return TreeNode(pointer.val)

            fast, slow, pre = pointer, pointer, None
            while fast is not None and fast.next is not None:
                fast = fast.next.next
                pre = slow
                slow = slow.next

            root = TreeNode(slow.val)
            pre.next = None  # 切断左子链与后面的连接, 进入递归
            root.left = get_root(pointer)
            root.right = get_root(slow.next)
            return root
        return get_root(head)

相关题目

• 数组版: 108. 将有序数组转换为二叉搜索树