在Python中将链表转换为之字形二叉树的程序

在Python中将链表转换为之字形二叉树的程序

假设我们有一个单向链表,我们必须使用以下规则将其转换为二叉树路径−

  • 链表的头是根。
  • 每个后续节点是父节点的左子节点当其值较小时,否则它将是右子节点。

所以,如果输入为[2,1,3,4,0,5],则输出将是

在Python中将链表转换为之字形二叉树的程序

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

  • 定义一个函数解决()。 这将带来一个节点
  • 如果节点为null,则
    • 返回null
  • root:=创建一个值与节点值相同的树节点
  • 如果节点的下一个值不为null,则
    • 如果节点的下一个值<节点的值,则
      • 根的左侧:= solve(节点的下一个值)
    • 否则,
      • root的右侧 := solve(下一个节点的值)
  • 返回root

让我们看下面的实现,以获得更好的理解。

示例

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next
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
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
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
         root = TreeNode(node.val)
      if node.next:
         if node.next.val < node.val:
            root.left = self.solve(node.next)
         else:
            root.right = self.solve(node.next)
      return root
ob = Solution()
L = make_list([2,1,3,4,0,5])
print_tree(ob.solve(L))

输入

[2,1,3,4,0,5]

输出

1, 3, 0, 5, 4, 2,

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程