將樹的層次遍歷轉換為 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 次瀏覽

啟動您的 職業

完成課程獲得認證

開始
廣告