将树的层次遍历转换为 Python 中的链表的程序

假设我们有一个二叉搜索树，我们必须使用层次遍历将其转换为单链表。

所以，如果输入类似于

那么输出将为 [5, 4, 10, 2, 7, 15, ]

为了解决这个问题，我们将按照以下步骤进行 −

  • head := 一个新的链表节点

  • currNode := head

  • q := 一个带有根值列表

  • 当 q 不为空时，执行

    • curr := 删除 q 中的第一个元素

    • 如果 curr 不为空，则

      • currNode 的 next := 一个带有 curr 值的新链表节点

      • currNode := currNode 的 next

      • 插入 q 末尾的 curr 左侧

      • 插入 q 末尾的 curr 右侧

  • 返回 head 的 next

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

示例

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.val = data
      self.left = left
      self.right = right

def print_list(head):
   ptr = head
   print('[', end = "")
   while ptr:
      print(ptr.val, end = ", ")
      ptr = ptr.next
print(']')
   
class Solution:
   def solve(self, root):
      head = ListNode(None)
      currNode = head
      q = [root]
      while q:
         curr = q.pop(0)
         if curr:
            currNode.next = ListNode(curr.val)
            currNode = currNode.next
            q.append(curr.left)
            q.append(curr.right)
      return head.next

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)
print_list(head)

输入

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)

输出

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

更新于： 2020 年 10 月 10 日

337 次浏览

启动您的 职业

完成课程获得认证

开始
广告