[Leetcode] 0297. バイナリツリーのシリアル化とデシリアル化

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

シリアル化とは、データ構造またはオブジェクトをビットのシーケンスに変換して、ファイルまたはメモリバッファーに保存したり、ネットワーク接続リンクを介して送信して、後で同じコンピューター環境または別のコンピューター環境で再構築できるようにするプロセスです。

バイナリツリーをシリアル化およびデシリアル化するアルゴリズムを設計します。シリアル化/デシリアル化アルゴリズムの動作方法に制限はありません。バイナリツリーを文字列にシリアル化でき、この文字列を元のツリー構造に逆シリアル化できることを確認するだけで済みます。

説明: 入力/出力形式は LeetCodeがバイナリツリーをシリアル化する方法。必ずしもこの形式に従う必要はありませんので、創造性を発揮して、自分でさまざまなアプローチを考え出してください。

例 1:

入力： ルート = [1,2,3,null,null,4,5]
出力： [1,2,3,null,null,4,5]

例 2:

入力： ルート = []
出力： []

制約:

ツリー内のノードの数は範囲内です [0, 10 ⁴ ].
-1000 <= ノード値 <= 1000

パイソン

				
					# 時間計算量: O(n) # 空間計算量: O(h) from collections import deque from entering import Optional class Codec: def serialize(self, root: Optional[TreeNode]) -> str: if not root: return '' queue = deque([root]) result = [] while queue: node = queue.popleft() if node: result.append(str(node.val)) queue.extend([node.left, node.right]) else: result.append('None') return ','.join(result) def deserialize(self, data: str) -> Optional[TreeNode]: if not data: return None dataList = data.split(',') root = TreeNode(int(dataList[0])) queue = deque([root]) i = 1 while queue and i < len(dataList): node = queue.popleft() leftVal, rightVal = dataList[i], dataList[i+1] if i + 1 < len(dataList) else 'None' if leftVal != 'None': node.left = TreeNode(int(leftVal)) queue.append(node.left) if rightVal != 'None': node.right = TreeNode(int(rightVal)) queue.append(node.right) i += 2 return root # Codec オブジェクトは次のようにインスタンス化され、呼び出されます: root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(5) root.left.left = TreeNode(3) root.left.right = TreeNode(4) ser = Codec() deser = Codec() tree = ser.serialize(root) print(tree) # '1,2,5,3,4,None,None,None,None,None,None,' ans = deser.deserialize(tree) print(ans.val) # 1 print(ans.left.val) # 2 print(ans.right.val) # 5 print(ans.left.left.val) # 3 print(ans.left.right.val) # 4

パイソン

関連記事