用 Python 创建链表到二叉搜索树的程序

pythonserver side programmingprogramming更新于 2026/1/19 9:48:17

假设我们有一个大小为 n 的排序链表节点，我们必须通过取 k = (n / 2) 的最小值的下限并将其设置为根来创建二叉搜索树。然后使用第 k 个节点左侧的链表递归构建左子树。并使用第 k 个节点右侧的链接列表递归构建右子树。

因此，如果输入为 [2,4,5,7,10,15]，则输出将是

为了解决这个问题，我们将遵循以下步骤−

定义一个方法solve()，它将获取节点
如果节点为空，则
- 返回null
如果节点的下一个为空，然后
- 返回一个值为 node 的新树节点
slow := node, fast := node
prev := None
当 fast 和 fast 的 next 不为空时，执行
- prev := slow
- slow := slow 的 next
- fast := fast 的 next 的 next
prev 的 next := None
root := 一个值为 slow 的新树节点
root 的 left := resolve(node)
root 的 right := 求解(慢速的下一个)
返回 root

让我们看看下面的实现以便更好地理解 −

示例

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right

def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
return head

def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)

class Solution:
   def solve(self, node):
      if not node:
         return None
      if not node.next:
         return TreeNode(node.val)
      slow = fast = node
      prev = None
      while fast and fast.next:
         prev = slow
         slow = slow.next
         fast = fast.next.next
      prev.next = None
      root = TreeNode(slow.val)
      root.left = self.solve(node)
      root.right = self.solve(slow.next)

      return root

ob = Solution()
head = make_list([2,4,5,7,10,15])
root = ob.solve(head)
print_tree(root)