Python程式：將連結串列轉換為之字形二叉樹

假設我們有一個單鏈表，我們需要使用以下規則將其轉換為二叉樹路徑：

  • 連結串列的頭節點作為根節點。
  • 每個後續節點，如果其值小於父節點的值，則成為父節點的左子節點，否則成為右子節點。

因此，如果輸入為 [2,1,3,4,0,5]，則輸出將為

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 solve()。它將接收一個節點作為引數。
  • 如果節點為空，則
    • 返回 null
  • root := 建立一個樹節點，其值與節點的值相同。
  • 如果節點的 next 不為空，則
    • 如果節點的 next 的值小於節點的值，則
      • root 的左子節點 := solve(節點的 next)
    • 否則，
      • root 的右子節點 := solve(節點的 next)
  • 返回 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,

更新於: 2020年11月19日

178 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告