代表的な面接トピック

コーディング面接：二分木の最小共通祖先（LCA）を見つける

コーディング普通
Offer.cc 編集チーム公開日 更新日

質問

任意の二分木のルートと、その木に含まれる2つの異なるノード p および q への参照が与えられたとき、それらの最小共通祖先を返してください。ノードの値は重複する可能性がありますが、p と q は木内に存在することが保証されています。アルゴリズムを実装し、正当性を証明し、計算量を分析した上で、極端な深さやターゲットが存在しない可能性がある場合にどのように適応させるかを説明してください。

問題と範囲

任意の二分木と、その木に含まれる2つの異なるノード p および q が与えられたとき、それらの最小共通祖先（LCA）を返します。ノードは自身自身の祖先でもあります。LCAは、その部分木が両方のターゲットを含む最も深いノードであるため、p が q の祖先である場合、答えは p 自身になります。

基本となる前提条件（契約）を定義する4つの詳細があります。木は二分探索木（BST）ではないこと、入力は値ではなくノードオブジェクトを識別すること、別々のノードが同じ値を持つ可能性があること、そして p と q の両方が木内に存在することが保証されていることです。値を比較することは暗黙のうちにその前提条件に違反します。また、存在保証を外した状態で基本の再帰を再利用すると、検出しにくい偽陽性が発生します。

text
a
      /   \
     b     c
    / \   / \
   d   e f   g
        \
         h

ここでは、LCA(d, h) = b、LCA(b, h) = b、および LCA(e, f) = a です。この問題は、木の走査、再帰のセマンティクス、および計算量を理解していることが期待されるソフトウェアエンジニアを対象としています。ベースケースでは1つのクエリが求められます。制限のない深さ、存在しないターゲット、親ポインタ、または1つの静的な木に対する多数のクエリは、最適な解法を変化させるフォローアップの制約です。

面接官が評価している点

最初の有益な着眼点は、「最も低い（lowest）」を構造に変換することです。答えは、ルートから p へのパスと、ルートから q へのパスにおける最後の共通ノードです。両方のパスを保存するのは正当ですが、不要です。より洗練された導出では、各部分木に次の3つの状態のいずれかを報告させます。ターゲットが見つからない、1つのターゲットが見つかった、または両方のターゲットがすでに合流したポイントである、の3つです。

優れた回答では、再帰の戻り値を正確に定義します。node を根とする部分木に対して、関数は以下を返します：

  • 部分木に p も q も含まれない場合は null；
  • 発見された1つのターゲットを上位に伝播する必要がある場合は p または q；
  • そのノードがこの部分木内ですでにLCAになっている場合は、その別のノード。

両方の再帰結果が非nullである場合、ターゲットは現在のノードの異なる側から合流するため、現在のノードが答えとなります。片側のみが非nullの場合、その結果が上に伝播します。存在が保証されているため、現在のノードがターゲットである場合、ベースケースは直ちにリターンします。もう一方のターゲットがその下にある場合、このノードがLCAになります。そうでなければ、このノードは祖先に1つのターゲットを報告しなければなりません。

契約の落とし穴は重要です。もし q が存在しない場合、基本アルゴリズムは p を返す可能性があり、両方のターゲットが存在することまでは証明しません。保証が取り除かれた場合、再帰結果には一致カウントが必要になります。n 個のノードと高さ h を持つ木の場合、1つのクエリは最悪の場合すべてのノードを訪問するため、時間は O(n) であり、再帰スタックは O(h) です。偏った（歪んだ）木では h = n となり、アルゴリズムの処理ではなくコールスタックが障害の原因になる可能性があります。

最初に明確にすべき質問

  • 入力はノードへの参照ですか、それとも値ですか？ 参照であれば重複値が許容されるため、node === p で比較します。値の検索は、一意性が前提条件の一部である場合にのみ有効です。
  • 両方のターゲットが存在し、かつ互いに異なることが保証されていますか？ 基本の再帰は存在を前提としています。どちらかが存在しない可能性がある場合は、一致カウントも返します。p === q が許容される場合、そのオブジェクトを1回見つければ十分かどうかを定義します。
  • これは任意の二分木ですか、それとも二分探索木ですか？ 任意の木には構造的な探索が必要です。BSTであれば1つのパスに沿ってキーの順序をたどることができますが、重複キーや参照の同一性によってそのショートカットが無効になる場合があります。
  • 最大ノード数と木の高さはどれくらいですか？ 平衡木では再帰の深さは O(log n) です。100,000ノードの一連の鎖のような木では、実行時のスタックオーバーフローを避けるために明示的なスタックと親マップが必要になります。
  • 同じ静的な木に対していくつのクエリが実行されますか？ 単一のクエリであれば直接のDFSが有利です。クエリが多数ある場合は、O(log n) クエリのために深さと 2^k の祖先を事前計算することを正当化できます。
  • ノードはすでに親ポインタを持っていますか？ それであればルートから走査する必要はありません。深さを揃えて一緒に上にたどるか、一方の祖先チェーンを記録して最初の交差を見つけます。

30秒の回答フレームワーク

「まず、これが任意の二分木であり、p と q が存在保証されたノード参照であるため、重複する値が同一性に影響しないことを確認します。私の再帰関数は、部分木で発見されたターゲットまたはLCAを返します。nullノードは null を返し、p または q に等しいノードはそれ自身を返します。両方の子を探索した後、2つの非null結果はターゲットが現在のノードで合流することを意味し、それ以外の場合は1つの非null結果を伝播します。各ノードは最大1回訪問されるため、最悪時間計算量は O(n)、スタックスペースは O(h) です。分岐した枝、一方が祖先となるターゲット、重複値、偏った木をテストします。ターゲットが存在しない可能性がある場合は一致カウントを追加し、高さが無制限の場合は明示的なスタックを使用して親リンクを構築します。」

ステップバイステップの解法

ステップ1：正しいパスのベースラインを確立する

最も直接的なアプローチは、ルートから p およびルートから q へのパスを見つけ、それらをルートから比較して、最後に共有されたノードを返すことです。これは定義を明確に説明し、両方のターゲットが存在することを自然に検証します。2回のDFSパスは依然として O(n) の時間がかかり、パスと再帰には O(h) の空間を使用します。探索されたすべてのノードを保持する実装では、O(n) の空間に増加する可能性があります。

冗長な点は、両方の探索が大きな共有プレフィックスを走査することです。必要な情報は部分木がその親に何を報告するかだけであるため、2つのパスは1回の後順走査に圧縮できます。

ステップ2：戻り値を定義し、1回だけ走査する

ts
interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null || root === p || root === q) {
    return root
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left !== null && right !== null) {
    return root
  }

  return left ?? right
}

コードはオブジェクトの同一性を比較し、value を読み取らないため、異なるノードに同じ値があっても安全です。後順走査は不可欠です。現在のノードは、自身が最初の合流ポイントであるかどうかを判断する前に、両方の子からのレポートを必要とするためです。

ステップ3：不変条件で証明する

node を根とする任意の部分木を考え、両方の再帰呼び出しが戻り値の定義を満たしていると仮定します。

  1. node が null の場合、部分木にはターゲットが含まれていないため、null が正しいです。
  2. node が p または q である場合、node を返します。両方のターゲットが存在するため、このターゲットはもう一方のターゲットを含んでいるためLCAであるか、または祖先に1つのターゲットを報告しなければなりません。
  3. 両方の子の結果が非nullである場合、それぞれの側がターゲットを報告しています。両方の側に属するより深いノードは存在しないため、node が最も深い共通祖先です。
  4. ちょうど片側だけが非nullである場合、現在のノードは新しい合流ポイントを作りません。その側のターゲットまたは完成したLCAが、伝播すべき唯一の有効な結果です。両方がnullの場合は null を返します。

構造的帰納法により、ルートで返される結果は木全体のLCAになります。この証明は、見落としがちな祖先のケースもカバーしています。p が q の祖先である場合、p に到達すると、q が下から2回目に返されることを要求することなくそれを返します。

ステップ4：実際の時間と空間のコストを述べる

最悪の場合、関数はすべての n 個のノードを訪問し、各ノードで定数時間の処理を行うため、時間は O(n) です。ターゲットに早く遭遇すると木の一部をスキップできますが、最良ケースは最悪ケースの境界ではありません。

補助空間は再帰のために O(h) です。平衡木では h = O(log n) ですが、完全に偏った木では h = n です。返されるノード参照は補助記憶域としてカウントされません。解法の空間計算量を O(1) と呼ぶのはコールスタックを無視しています。

ステップ5：ターゲットが存在しない可能性がある場合に契約を変更する

存在保証がない場合、基本関数は誤った結果を返す可能性があります。木内に p しか出現しない場合、p をルートまで伝播してしまいます。安全なバージョンでは、候補ノードと実際に見つかったターゲットの数を区別します。

ts
interface SearchResult {
  candidate: TreeNode | null
  matches: number
}

function lowestCommonAncestorValidated(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function visit(node: TreeNode | null): SearchResult {
    if (node === null) {
      return { candidate: null, matches: 0 }
    }

    const left = visit(node.left)
    if (left.matches === 2) {
      return left
    }

    const right = visit(node.right)
    if (right.matches === 2) {
      return right
    }

    const self = node === p || node === q ? 1 : 0
    const matches = left.matches + right.matches + self

    return {
      candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
      matches,
    }
  }

  const result = visit(root)
  return result.matches === 2 ? result.candidate : null
}

このバージョンは依然として p !== q を前提としています。同じ参照が2回与えられる可能性がある場合は、まず契約を定義してください。そのノードを1回見つけたら、matches === 2 を要求し続けるのではなく、それを返す必要があります。コードの変更よりも制約の変更を先行させるべきです。

ステップ6：深い木に対して明示的なスタックと親マップを使用する

木の高さが100,000に近づく可能性がある場合、漸近的な再帰空間は変わりませんが、実行時のコールスタックが先にオーバーフローする可能性があります。明示的なスタックで走査し、p と q の両方がマップに含まれるまで parent.get(child) = node を記録します。p のすべての祖先をセットに入れ、その後 q から上にたどります。セットに最初に含まれていたメンバーがLCAです。

この代替案も依然として O(n) の時間であり、O(n) の明示的な空間を使用します。再帰よりも多くのヒープメモリを使用する可能性がありますが、リソースを小さなコールスタックから制御されたデータ構造へと移行させます。妥当な高さの制限がある木に対する単一のクエリでは、再帰バージョンのほうが短く証明しやすいため、親マップを自動的なデフォルトにすべきではありません。

ステップ7：エッジケースや対抗ケースでセマンティクスを検証する

最低限、このマトリクスをカバーしてください：

ケース期待される結果検出されるバグ
p と q がルートの反対側の枝にあるルート片方のパスしか探索していない
p が q の祖先であるp自身が祖先であることを忘れている
両方のノードが1つの部分木の深いところにある部分木のノード高すぎる祖先を返している
異なるノードが等しい value を持っている同一性による正しいオブジェクト値を同一性として扱っている
拡張契約下での p === q を持つ1ノードの木そのノード同一ターゲットの動作が未定義
1つのターゲットが存在しない検証済みバージョンは null を返す基本バージョンの偽陽性
100,000ノードの直線状の木反復バージョンが完了する再帰スタックオーバーフロー

固定された例だけでなく、ランダムな小さな木を生成し、オブジェクトの同一性によってワンパスの結果をパスベースラインと比較します。ベースラインと最適化された手法は異なるアプローチを使用しているため、この差分チェックは少数の手動アサーション単体よりも多くの欠陥を捉えます。

高品質な回答例

「まず前提条件（契約）を固定します。これは任意の二分木であり、p と q は存在が保証された異なるノード参照であり、値は重複する可能性があります。したがって、私のコードは値ではなく参照を比較します。

私は1回の後順DFSを使用します。部分木に対して、関数は null、発見された1つのターゲット、またはすでに見つかったLCAを返します。nullノードは null を返し、いずれかのターゲットと等しい現在のノードはそれ自身を返します。両方の子に再帰した後、2つの非null結果はターゲットが現在のノードで最初に合流することを意味するため、それを返します。非nullの側が1つだけの場合は、その結果を伝播します。

正当性はその戻り値の不変条件から導かれます。ターゲットが異なる子部分木にある場合、両方を含むことができる、より深いノードは存在しません。一方が他方の祖先である場合、祖先ターゲットを直ちに返すことが定義に合致しています。最悪ケースでは各ノードを1回訪問するため時間は O(n) であり、再帰スタック空間は O(h) です。偏った木ではスタックの深さが O(n) になります。

反対側の枝、祖先となるターゲット、1つの深い部分木、および重複する値をテストします。ターゲットの存在が保証されていない場合、この関数は存在する1つのターゲットを返してしまう可能性があるため、一致カウントも返し、両方が見つかった後にのみ候補を受け入れます。木が非常に深くなる可能性がある場合は、コールスタックのオーバーフローを避けるために明示的なスタックと親マップを使用します。」

よくある間違い

  • 木をBSTとして扱い、値によって左右を選択する → 任意の二分木にはキーの順序がなく、重複する値はノードを識別しません → 構造を探索し、ノード参照を比較してください。
  • どちらかの子が非nullのときに現在のノードを返す → 片側の単一ターゲットがルートまで昇格してしまいます → 両側が非nullの場合にのみ現在のノードを返し、そうでない場合は非nullの結果を伝播してください。
  • p が答えの厳密に下になければならないと仮定する → ノードはそれ自身の祖先であるため、p が答えになり得ます → 現在のノードの同一性をベースケースに含めてください。
  • ターゲットが存在しない可能性がある場合に基本アルゴリズムを再利用する → 1つのターゲットが見つかっただけでも非nullの結果が生成されます → 一致カウントを返し、両方が見つかった後にのみ成功としてください。
  • 補助空間が O(1) であると主張する → 再帰フレームは木の高さとともに増大し、鎖状の木では O(n) に達します → O(h) と報告し、深さが無制限の場合は明示的なスタックを使用してください。
  • 単一のクエリに対してダブリング（binary lifting）を事前計算する → コードの複雑さと O(n log n) の記憶域が償却されません → 単一クエリには1回のDFSを使用し、クエリが多数ある場合にのみ前処理を行ってください。
  • 反対側にある2つの葉ノードのみをテストする → 祖先、重複値、存在しないターゲット、および深さに関するバグが隠れたままになります → 契約の境界を中心にテストを構成してください。

フォローアップの質問

p または q が木内に存在しない可能性がある場合はどうしますか？

再帰から候補ノードと一致カウントの両方を返します。個別のターゲットの場合、カウントは 0、1、または 2 になります。ルートの結果のカウントが 2 である場合にのみ候補LCAを返し、それ以外の場合は null を返します。存在する1つのターゲット自体が非nullであるため、基本アルゴリズムを実行して非null結果を確認するだけでは不十分です。

木が100,000ノードを持ち、完全に偏っている可能性がある場合はどうしますか？

明示的なスタックを使用して親マップを構築します。両方のターゲットが見つかったら、p の祖先をセットに保存し、q の親チェーンを最初の交差までたどります。これには O(n) の時間と O(n) のヒープ空間がかかりますが、100,000個の言語コールフレームを消費しません。ヒープ空間も制約されている場合は、再帰が安全であると思い込まずに、親ポインタまたは制御された走査インターフェースが利用可能かどうかを確認してください。

同じ静的な木に対して100万回のLCAクエリに答える必要がある場合はどうしますか？

クエリごとに O(n) のDFSを行うのはもはや適していません。O(n log n) の時間と空間で、各ノードの深さとその 2^k 番目の祖先を事前計算します。クエリごとに、より深いノードを同じ深さまで引き上げ、その後最大の k から下に向かって両方を引き上げることで、クエリあたり O(log n) になります。さらにクエリ量が多い場合は、オイラーツアーとRMQの組み合わせを検討する価値があります。更新頻度、メモリ、およびレイテンシの要件によって、適切な前処理方式が決まります。

すべてのノードがすでに親ポインタを持っている場合はどうしますか？

ルートから走査する必要はありません。両方の深さを計算し、深さが一致するまで深い方のノードを引き上げ、その後両方が等しくなるまで一緒に上に移動させます。これには O(h) の時間と O(1) の追加空間がかかります。あるいは、p のすべての祖先を保存し、q から上にたどることもできます。これはより単純ですが、O(h) のセットを使用します。

二分探索木の場合、解法はどう変わりますか？

キーが一意であり、キーによってターゲットを特定する契約の場合、両方のターゲットキーが小さい場合は左へ、両方が大きい場合は右へ進み、それ以外の場合は現在の分岐ポイントまたはターゲットを返します。これには O(h) の時間と O(1) の反復空間がかかります。値が重複する可能性がある場合、または入力が依然として参照によってターゲットを識別する場合は、まず重複キーの配置と検索セマンティクスを定義してください。2つの値だけでは、任意の木に対するアルゴリズムを安全に置き換えることはできません。

公開情報ソース

Meta Interview Question: Given two node values in a binary tree, what is their lowest common ancestor?

Glassdoor

Meta software engineer, Machine learning

Reddit

E5 Meta Phone screen

Interview Experiences

Lowest Common Ancestor of a Binary Tree

LeetCode

题解 | 〖模板〗最近公共祖先（LCA）

牛客网

関連する質問

コーディング面接：単調デック（Monotonic Deque）を用いてスライディングウィンドウの最大値を解く方法質問と回答を開くコーディング面接：二分木のシリアライズとデシリアライズ質問と回答を開くコーディング面接：データストリームからの中央値の取得質問と回答を開く

関連面接ツール

コーディング問題にはスクリーンショットを使用

問題をキャプチャし、制約条件、解法アプローチ、コード、エッジケース、計算量の順に進めます。

ツールを見る
無料で登録