题目描述
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)
相关题目