問題と適用コンテキスト
任意の二分木に対して次の2つの関数を実装してください。
serialize(root)は木を文字列に変換します。deserialize(data)は同じ値と形状を持つ木を再構築します。
ノードの値は符号付き32ビット整数であり、木は空である可能性があり、シリアライズされた文字列はこのデコーダとのみ相互運用できればよいと仮定します。面接での再帰的実装では、木の高さが言語のコールスタック制限内に収まるものとします。以下のデコーダは、部分木を暗黙的に受け入れるのではなく、不正なテキストを拒絶します。
この木の場合：
1
/ \
2 3
/ \
4 5選択されたフォーマットは次のとおりです：
1,2,#,#,3,4,#,#,5,#,#各整数はノードを記録し、# は欠落している子ノードを記録し、カンマでトークンを区切り、先行順走査によってトークンの消費順序が決定されます。2026年に更新された公開資料では、先行順および幅優先（level-order）の解法を用いてまさにこの問題が提示されており、interviewing.io の再現動画でも Meta のエンジニアによる模擬面接で出題されています。これは、すべての企業や面接で出題されると主張するものではありませんが、現在でも代表的なコーディング課題であることを示しています。
面接官が評価しているポイント
最初の評価シグナルは、候補者が走査方法を選択する前に「可逆性」を定義しているかどうかです。先行順の値だけでは不十分です。左の子 2 を持つ根 1 と、右の子 2 を持つ根 1 は、欠落した子ノードをエンコードしない限り、どちらも [1, 2] を生成してしまいます。マーカーを付与した形式では違いが現れます：
Left child: 1,2,#,#,#
Right child: 1,#,2,#,#2つ目のシグナルは、エンコーダとデコーダを逆演算として設計することです。先行順では、デコーダは1つのトークンを読み取ります。# は空の部分木を完了します。値はノードを開始し、その後の次の完全な部分木は左の子に属し、それに続く完全な部分木は右の子に属します。したがって、このフォーマットは部分木の長さを保存することなく、自身の再帰的境界を提供します。
3つ目のシグナルは、正当性の根拠となる論理的な説明です。n 個のノードを持つ木には、n + 1 個の null 子ポインタが存在するため、エンコーディングには正確に 2n + 1 個のトークンが含まれます。さらに重要なのは、デコーダが1つの部分木に対応するトークンを正確に消費し、イテレータを次の部分木の位置に残す必要があるという点です。構造帰納法によりこの性質が証明されます。
最後に面接官は、不正な入力、負の値や重複値、再帰の深さ、出力サイズ、そして BFS や本番環境向けシリアライズフォーマットが適しているケースなど、エンジニアリング上の境界条件を適切に捉えているかを確認します。
回答前の明確化のための質問
- これは任意の二分木ですか、それとも二分探索木（BST）ですか？ 任意の二分木には構造マーカーが必要です。BST の場合は、先行順走査と重複に対する明示的なポリシーがあれば再構築できることがあります。
- 文字列は既存の通信フォーマットに従う必要がありますか？ この設問では独自のフォーマットが許可されています。サービス間ストレージでは、スキーマのバージョニング、互換性ルール、標準コーデックが必要になることがよくあります。
- ノードの値に区切り文字や番兵を含めることはできますか？ 値は整数であるため、カンマや
#と衝突せず明確です。一般的な文字列の場合は、エスケープや長さプレフィックスが必要になります。 - 木が空になることはありますか？ はい。その場合は
#にシリアライズされます。 - 入力が極端に深い、または悪意のあるものである可能性はありますか？ 再帰による解法は高さが制限されていることを前提としています。信頼できない木や極端に偏った木には、明示的なスタックとリソース制限が必要です。
deserializeはserializeからの信頼できる出力のみを受け取りますか？ コードは厳格に保ちます。空のテキスト、不正な整数、途中で切れた木、余分な末尾トークンは拒絶されます。- 可読性と最小バイト数のどちらを最適化しますか？ 先行順テキストは説明やテストが容易です。コンパクトなバイナリプロトコルの場合、タグと整数のエンコード方法が異なります。
30秒の回答フレームワーク
「先行順走査を使用し、欠落している子ノードごとに # を出力します。値トークンはノードを作成し、その左と右の部分木を再帰的にデコードすることを意味します。# は None を返すことを意味します。値だけでは左の子と右の子を区別できないため、null マーカーが必要です。エンコーダとデコーダは互いに鏡像関係にあり、構造帰納法によって各デコード呼び出しが正確に1つの部分木を消費することが示されます。両方の操作は時間計算量 O(n)、データ空間量 O(n) であり、高さ h に対して O(h) のコールスタックを使用します。また、途中で切れた入力や末尾の余分な入力を拒絶し、深さが無制限の場合は反復的な BFS やスタックベースのバージョンについても言及します。」
ステップバイステップの詳細解説
ステップ 1：値のみのベースラインを反例によって否定する。
先行順、中間順（inorder）、後続順（postorder）の値だけでは、任意の二分木を一意に特定できません。先行順と中間順を組み合わせたとしても、値の重複が許可されている場合は曖昧になります。フォーマットは値だけでなく形状もエンコードしなければなりません。null マーカーは、面接での文字列フォーマットにおいて最もシンプルな形状シグナルです。
ステップ 2：左から右へデコード可能な文法を選択する。
このフォーマットは再帰的に記述できます：
tree := "#"
| integer "," tree "," tree実際の実装では最初にカンマでトークン化するため、各再帰呼び出しは1つのトークンを消費し、値の場合はそれに続く2つの部分木のエンコーディングを消費します。符号付き整数のテキストに , や # が含まれることはありません。空の木は # であり、値 7 を持つ葉ノードは 7,#,# です。
この文法には便利なカウント不変条件もあります。n 個の実ノードを持つ二分木には、n + 1 個の null 子ポインタが存在します。したがって、シリアライズでは n 個の値トークンと n + 1 個の null トークンが出力され、合計で 2n + 1 個のトークンになります。このカウントは診断用であり、パースの代用にはなりません。トークンが不正であっても合計が奇数になることはあり得ます。
ステップ 3：鏡像となる再帰操作を実装する。
from __future__ import annotations
from dataclasses import dataclass
MIN_INT32 = -(2**31)
MAX_INT32 = 2**31 - 1
@dataclass
class TreeNode:
val: int
left: TreeNode | None = None
right: TreeNode | None = None
class Codec:
NULL = "#"
SEP = ","
def serialize(self, root: TreeNode | None) -> str:
tokens: list[str] = []
def visit(node: TreeNode | None) -> None:
if node is None:
tokens.append(self.NULL)
return
if node.val < MIN_INT32 or node.val > MAX_INT32:
raise ValueError("node value is outside signed 32-bit range")
tokens.append(str(node.val))
visit(node.left)
visit(node.right)
visit(root)
return self.SEP.join(tokens)
def deserialize(self, data: str) -> TreeNode | None:
if data == "":
raise ValueError("serialization cannot be empty")
tokens = iter(data.split(self.SEP))
def build() -> TreeNode | None:
try:
token = next(tokens)
except StopIteration:
raise ValueError("serialization is truncated") from None
if token == self.NULL:
return None
try:
value = int(token)
except ValueError:
raise ValueError(f"invalid integer token: {token}") from None
if value < MIN_INT32 or value > MAX_INT32:
raise ValueError("node value is outside signed 32-bit range")
node = TreeNode(value)
node.left = build()
node.right = build()
return node
root = build()
try:
extra = next(tokens)
except StopIteration:
return root
raise ValueError(f"trailing token: {extra}")トークンリストを構築することで、シリアライズ中の文字列の反復結合を回避します。デコーダは再帰呼び出し間で1つのイテレータを共有するため、子が先頭から再読み込みすることはありません。根の処理完了後にトークンが残っていないかチェックすることで、1,#,#,9,#,# のような有効なプレフィックスを持つ不正な入力が受け入れられるのを防ぎます。
ステップ 4：デコードがシリアライズの逆操作であることを証明する。
木 T に対する構造帰納法を使用します。
- 基底条件：
Tが空の場合、シリアライズは#を出力します。デコーダは#を読み取り、Noneを返し、その部分木の1つのトークンを正確に消費します。 - 帰納フェーズ：左と右の部分木に対して主張が成り立つと仮定します。シリアライズは根の値を出力し、その後に完全な左のエンコーディング、そして完全な右のエンコーディングを出力します。デコーダは同じ根を作成し、帰納法の仮定により最初の再帰呼び出しは正確に左のエンコーディングを消費し、2回目の呼び出しは正確に右のエンコーディングを消費します。同じ形状と値を再構築し、
Tの直後で停止します。
したがって deserialize(serialize(T)) は T と構造的に等しく、各呼び出しはイテレータを次の未読の部分木の位置に残します。最後の末尾トークンチェックにより、根が入力全体を消費したことが検証されます。
ステップ 5：出力やスタックを隠さずにコストを計算する。
両方の操作は各実ノードと null ポインタを1回ずつ訪問するため、時間は O(n) です。シリアライズされた出力およびトークン化された入力は O(n) です。再構築された木自体も O(n) です。再帰呼び出しスタックの使用量は O(h) です。ここで h は木の高さであり、平衡木では O(log n)、完全に偏った木では O(n) となります。
高さが制限されており明瞭さが重視される場合、再帰コードは面接の良い回答となります。ただし、ランタイムの再帰制限を超えるような攻撃者制御のチェーンに対しては安全ではありません。その場合は、明示的なスタックまたはレベル順キューを使用し、最大ノード数、トークン数、バイト数、および深さの制限を適用してください。
ステップ 6：先行順 DFS とレベル順 BFS を比較する。
どちらも null 情報を保持していれば、時間 O(n) および出力空間で可逆となります。
| フォーマット | 主な利点 | 主なコスト |
|---|---|---|
| null 付き先行順 DFS | エンコーダとデコーダが同じ再帰構造を持つ | 再帰版は O(h) のコールスタックを使用する |
| null 付きレベル順 BFS | 反復処理であり、配列による木の表現例と視覚的に近い | キューが O(w) 個のノードを保持する可能性があり、疎な木では出力が冗長になり得る |
| 値のみ | 短い | 任意の木の構造が失われる |
| 標準のバージョニング付きバイナリ形式 | 相互運用性とコンパクトな型付きフィールド | この面接で求められる以上のプロトコルの仕組みが必要 |
再帰の深さが差し迫ったリスクである場合や、周囲のシステムがすでにレベル順の表現を使用している場合は、BFS が好まれます。一方、文法と証明がシンプルであるため、面接の基本回答としては先行順が好まれます。
ステップ 7：ラウンドトリップと不正な入力を検証する。
ラウンドトリップテストでは以下をカバーする必要があります：
| ケース | 期待されるシリアライズ結果 |
|---|---|
| 空の木 | # |
単一ノード 7 | 7,#,# |
根 1、左の子 2 | 1,2,#,#,# |
根 1、右の子 2 | 1,#,2,#,# |
| 負の重複した子ノード | 構造と両方の重複値が保持される |
| 符号付き32ビットの極値 | 両方の境界値がパースされラウンドトリップする |
また、""、1,#、x,#,#、2147483648,#,#、1,#,#,2,#,# も拒絶します。生成された木に対しては、元の木とデコードされた木を再帰的に比較し、serialize(deserialize(serialize(root))) == serialize(root) をアサートします。偏った木のテストは、許容される高さの境界付近で実行し、スタックの前提が偶発的ではなく明示的であることを確認する必要があります。
質の高い模範回答
「まず、これが任意の二分木であり、値が符号付き32ビット整数であり、フォーマットが当社のデコーダでのみ読み取れればよいことを確認します。重複値が許可されているため、構造を明示的にエンコードする必要があります。
先行順で走査します。実ノードに対してはその値を出力し、続いて左と右の部分木を出力します。欠落している子ノードに対しては # を出力します。これにより、たとえば先行順の値が同一であっても、左の子と右の子を区別できます。デコード中は、1つの共有トークンイテレータが同じ文法を反映します。# は None を返し、それ以外の場合はノードを作成して左、右の順に再帰的に構築します。
正当性は構造帰納法により導かれます。空の木は1つの # です。実際の実ノードの根について、各再帰呼び出しが正確に1つの子の部分木を再構築して消費すると仮定すると、2回の呼び出しはシリアライズされた左と右の部分を順番に消費し、元の根を再構築します。途中で切れた終端、不正または範囲外の値、および末尾の余分なトークンは拒絶します。
各実ノードと null ポインタは1回処理されるため、両方の操作は O(n) です。テキストとトークンは O(n) の空間を使用し、再帰は O(h) のスタックを使用します。木の高さが悪意を持って深くなる可能性がある場合は、明示的なスタックまたは BFS に切り替え、サイズと深さの制限を設けます。空、単一ノード、左のみ vs 右のみ、重複、負の値、整数の境界値、不正な文字列、およびランダムなラウンドトリップをテストします。」
よくある間違い
- ノードの値のみをシリアライズする → 異なる形状でも同じ走査結果になる場合がある → null マーカーやその他の明示的な構造境界を出力する。
- 値の内部に出現しうる区切り文字を使用する → トークンの境界が曖昧になる → 値をエスケープするか、長さを付与するか、値の文法外の区切り文字を選択する。
- 再帰呼び出しごとに新しいイテレータを作成する → 各子が最初のトークンを再読み込みしてしまう → 進行する1つのイテレータまたはインデックスを共有する。
- 根をデコードした後に残りのテキストを無視する → 有効なプレフィックスによって末尾の破損データが見過ごされる → 入力が完全に消費されることを要求する。
- 欠落したトークンを無関係な例外として発生させる → 途中で切れたデータの診断が困難になる → 途中のデータ不足を明確なパースエラーに変換する。
- 補助空間が常に
O(log n)であると主張する → 偏った木の高さはnであり、トークン化も線形空間を使用する → 出力、トークンストレージ、木、コールスタックのコストを分けて考える。 - 重複を定義せずに BST では先行順の値だけで十分であるとする → 同一のキーにより再構築が曖昧になる可能性がある → マーカーを省く前に順序付けと重複ポリシーを明記する。
- 信頼できない深さに対して制限なしで再帰コードを使用する → 長いチェーンによってスタックが枯渇する可能性がある → 明示的なスタックとリソース制限を使用する。
- ラウンドトリップ後にオブジェクトの同一性（参照）を比較する → 再構築により新しいノードが作成される → 値と構造を比較する。
- 平衡木の例のみをテストする → 左右の曖昧さやスタックのリスクが隠れたままになる → 空、片側のみ、重複、極値、不正入力、偏った木のケースを含める。
フォローアップの質問と回答
フォローアップ 1：二分探索木（BST）では null マーカーを省略できますか？
多くの場合、省略可能です。厳密な BST 不変条件とユニークなキーがあれば、下限値と上限値を保持することで先行順から再構築できます。現在の範囲内の値はその部分木に属し、範囲外の最初の値は祖先ノードに属します。重複が許可されている場合、契約において等しい値が左に行くか、右に行くか、ノード内でカウントされるかを定義する必要があります。そのポリシーがない場合、コンパクトなフォーマットは曖昧になります。任意の木を扱う基本問題ではこの最適化は使用できません。
フォローアップ 2：任意の文字列値をサポートするにはどうしますか？
カンマや # が文字列内に現れる可能性があるため、区切り文字による分割だけでは自己完結的な区切りになりません。1つの選択肢は 5:hello のような長さプレフィックスを使用し、その後に明示的なノード/null タグを続けることです。もう1つの選択肢は、スキーマを持つ標準のシリアライズライブラリを使用することです。エスケープも機能しますが、デコーダはエスケープされた区切り文字と構造上の区切り文字を区別し、無効なエスケープシーケンスを処理する必要があります。長さプレフィックスを使用すると、消費ルールの証明が容易になります。
フォローアップ 3：数百万ノードの木や極端な深さの木に対しては何を変更しますか？
ピークメモリが問題になる場合は、再帰呼び出しを避け、入力全体の一括分割を避けます。子のスロットを管理する明示的なスタックを備えた反復パーサーを通じてトークンをストリーミング処理し、すべてのトークンを最初に収集するのではなくライターへ出力をストリーミングします。無制限の状態を割り当てる前に、最大バイト数、トークン数、ノード数、整数長、および深さの制限を適用します。時間は O(n) のままですが、メモリはアクティブなスタックまたはキューに加え、出力バッファポリシーに応じたものになります。
フォローアップ 4：本番システムでこのフォーマットをバージョニングするにはどうしますか？
木のペイロードの外部にフォーマット識別子とバージョンを追加し、整数の幅とテキストエンコーディングを定義し、未知のフィールドやバージョンに対して fail-closed（安全側に倒して拒否）とするかを指定します。破損を検出する必要がある場合は整合性チェックを含めますが、チェックサムを認証として扱わないでください。ロールアウトには古い形式の読み取り／新しい形式の書き込みの互換性と、サポートされる各バージョンのフィクスチャが必要です。クロスランゲージなサービスでは、面接用のコーデックを拡張するよりも、保守されたスキーマベースのフォーマットを使用する方が通常は安全です。
フォローアップ 5：レベル順シリアライズで末尾の null を安全に切り捨てることはできますか？
はい、デコーダが最後のリモート実ノードの後の省略された位置を null として定義し、シリアライザが末尾の連続する null マーカーのみを切り捨てる場合は可能です。途中の null を削除してはなりません。後続のノードの子の配置がずれてしまうためです。切り捨て後のラウンドトリップ契約と不正入力ルールをテストする必要があります。「短い配列のように見える」ことは等価性の証明にはなりません。