二分木のシリアライゼーションとデシリアライゼーション
二分木を文字列にシリアライズして再構築する方法を学びます。null マーカー付き行きがけ順、レベル順エンコーディング、LeetCode #297 のアプローチをカバーします。
Algorithms
詳細な説明
木のシリアライゼーションとデシリアライゼーション
シリアライゼーションは二分木を保存や送信が可能な文字列表現に変換します。デシリアライゼーションはその文字列から元の木を再構築します。この往復はロスレスでなければなりません。
アプローチ 1：null マーカー付き行きがけ順
最も一般的なアプローチは行きがけ順走査を使用し、null の子に特別なマーカー（"null" や "#"）を挿入します。
例
木: シリアライズ:
1 "1,2,null,null,3,4,null,null,5,null,null"
/ \
2 3
/ \
4 5
アプローチ 2：レベル順（BFS）エンコーディング
レベルごとにシリアライズし、null マーカーを含めます。これは LeetCode の木ビジュアライザーや多くのオンラインジャッジで使用されるフォーマットです。
なぜ通りがけ順だけではダメなのか？
通りがけ順走査だけでは二分木を一意に再構築できません。異なる木構造が同じ通りがけ順シーケンスを生成する可能性があるためです。必要なのは：
- 行きがけ順 + 通りがけ順（null マーカー不要）
- 帰りがけ順 + 通りがけ順
- null マーカー付き行きがけ順（単一走査）
- null マーカー付きレベル順（単一走査）
エッジケース
- 空の木: "null" にシリアライズ
- 単一ノード: "1,null,null" にシリアライズ
- 偏った木: 片側に多くの連続 null マーカー
ユースケース
木のシリアライゼーションは LeetCode #297（最も頻出のハード問題の1つ）、分散システム（ネットワーク上での木データの送信）、キャッシュ（計算済み木結果の保存）、データベースストレージ（入れ子集合モデル、マテリアライズドパス）、設定ファイル（階層データの表現）に現れます。JSON 自体が木のシリアライゼーションの一形態です。