Python程序：将链表转换为二叉搜索树

假设我们有一个大小为 n 的已排序链表节点，我们需要创建一个二叉搜索树。方法是：取 k = floor(n / 2) ，将第 k 个节点的值设置为根节点。然后，递归地使用链表中第 k 个节点左侧的节点构建左子树，并递归地使用链表中第 k 个节点右侧的节点构建右子树。

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

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

  • 定义一个名为 solve() 的方法，它将接收一个节点作为参数。

  • 如果节点为空，则

    • 返回 null

  • 如果节点的下一个节点为空，则

    • 返回一个值为该节点值的新树节点。

  • slow := node, fast := node

  • prev := None

  • 当 fast 和 fast 的下一个节点都不为空时，执行以下操作：

    • prev := slow

    • slow := slow 的下一个节点

    • fast := fast 的下一个节点的下一个节点

  • prev 的下一个节点 := None

  • root := 一个值为 slow 的新树节点

  • root 的左子节点 := solve(node)

  • root 的右子节点 := solve(slow 的下一个节点)

  • 返回 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)

输入

[2,4,5,7,10,15]

输出

2, 4, 5, 7, 10, 15,

更新于：2020年10月10日

960 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告