Pythonでレベルオーダーの二分木トラバーサルをリンクリストに変換するプログラム

二分探索木があるとすると、レベルオーダートラバーサルを使用してそれを単一リンクリストに変換する必要があります。

したがって、入力が次のような場合

その場合、出力は[5、4、10、2、7、15、]

これを解決するには、次の手順に従います-

• head：=新しいリンクリストノード

• currNode：=head

• q：=値rootのリスト

• qが空でない間、実行します

  • curr：=qから最初の要素を削除

  • currがnullでない場合、

    • currNodeの次：=currの値を持つ新しいリンクリストノード

    • currNode：=currNodeの次

    • qの最後にcurrの左側を挿入します

    • qの最後に右のcurrを挿入します

• 頭の次を返す

理解を深めるために、次の実装を見てみましょう-

例

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, ]