题目

109. Convert Sorted List to Binary Search Tree

Given the head of 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 1:

Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5]

Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST. Example 2:

Input: head = [] Output: []

Example 3:

Input: head = [0] Output: [0]

Example 4:

Input: head = [1,3] Output: [3,1]

Constraints:

The number of nodes in head is in the range [0, 2 * 10^4].-10^5 <= Node.val <= 10^5

解法一：转为数组后，根据数组序号二分组装成二叉排序树

思路： 因为树有左右分叉，用递归解法。

把链表的值，组装成数组；根据数组的索引，递归调用组装成二叉排序树 # Definition for singly-linked list. 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 ConvertSortedListToBinarySearchTree: # Convert the given linked list to an arry def mapListToValues(self, head: ListNode): vals = [] while head: vals.append(head.val) head = head.next return vals def sortedListToBST(self, head: ListNode) -> TreeNode: # check edge if head == None : return None if head.next == None: return TreeNode(head.val) # 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]) # Baes case for when there is only one element left in the array if l == r: return node # Recursively fom 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)

解法二：找链表中的中间节点，组装成二叉排序树

组装树的方法是用递归，如果能持续找到中间节点，就可以持续组装树的middle, middle.left, middle.right. 找中间节点的方法，用快慢两个指针，慢指针每次走一步，快指针每次走两步；这样子就可以找出中间节点。

# Definition for singly-linked list. 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 ConvertSortedListToBinarySearchTree: def findMiddle(self, head: ListNode): # The pointer used to disconnect the left half from the mid node. preNode = None slowNode = head fastNode = head # Iterate until fastNode doesn't reach the end of the linked list. while fastNode and fastNode.next: preNode = slowNode slowNode = slowNode.next fastNode = fastNode.next.next # Handling the case when slowNode was equal to head if preNode: preNode.next = None return slowNode def sortedListToBST2(self, head: ListNode): # If the head doesn't exist, then the linked list is empty if not head: return None # Find the middle element for the list mid = self.findMiddle(head) # the mid becones the root of the BST. node = TreeNode(mid.val) # Base case when there is just one element in the linked list if head == mid: return node # Recursively form balanced BSTs using the left and right halves of the original list. node.left = self.sortedListToBST2(head) node.right = self.sortedListToBST2(mid.next) return node

参考

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/solution/