用 Python 将层序二叉树遍历转换为链表的程序

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

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

因此，如果输入如下

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

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

head := 一个新的链表节点
currNode := head
q := 值为 root 的列表
当 q 不为空时，执行
- curr := 从 q 中删除第一个元素
- 如果 curr 不为空，则
  - currNode 的下一个 := 值为 curr 的新链接列表节点
  - currNode := currNode 的下一个
  - 在 q 末尾插入 curr 的左侧
  - 在 q 末尾插入右侧 curr
返回 head 的下一个

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

示例

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)