この記事では、LeetCode 235「二分探索木の最小共通祖先」の解法を、問題解決のアプローチやアルゴリズムの手順から時間計算量や空間計算量まで、完全に解説します。また、境界ケースをまとめ、3つの解法を比較することで、「二分探索木の最小共通祖先」を一度に理解できるようにサポートします。
Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリ リンク
バイナリ検索ツリー (BST) が与えられた場合、BST 内の 2 つの指定されたノードの最下位共通祖先 (LCA) ノードを検索します。
によると、 WikipediaにおけるLCAの定義: 「最下位共通祖先は2つのノード間で定義されます p そして q 最下位ノードとして T 両方を兼ね備えた p そして q 子孫として( 自身の子孫となるノード)」
例 1:

入力: 根 = [6,2,8,0,4,7,9,null,null,3,5]、p = 2、q = 8 出力: 6 説明: ノード 2 と 8 の LCA は 6 です。
例 2:

入力: 根 = [6,2,8,0,4,7,9,null,null,3,5]、p = 2、q = 4 出力: 2 説明: LCA 定義によれば、ノードは自身の子孫になることができるため、ノード 2 と 4 の LCA は 2 です。
例 3:
入力: 根 = [2,1]、p = 2、q = 1 出力: 2
制約:
- ツリー内のノードの数は範囲内です
[2, 10 5 ]. -10 9 <= ノード値 <= 10 9- 全て
Node.valは 個性的. p != qpそしてqBST に存在します。
パイソン
# バイナリ ツリー ノードの定義。 # クラス TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None クラス ソリューション: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': p.val < root.val かつ q.val < root.val の場合: self.lowestCommonAncestor(root.left, p, q) を返します p.val > root.val かつ q.val > root.val の場合: self.lowestCommonAncestor(root.right, p, q) を返します root を返します
LeetCode問題拡張演習
同じシリーズの他の問題解決ノートも練習用としてお勧めします。
さらに詳しく知りたい方はこちらをご覧ください
二分探索木の最小共通祖先:解法
二分探索木(BST)の順序性を利用することで、この問題は簡略化できます。両方の目標値が現在のノードより小さい場合、答えは左部分木に存在し、両方が大きい場合は右部分木に存在します。また、「一方が他方より小さい」または「どちらか一方が現在のノードと等しい」場合は、現在のノードが最小共通祖先となります。バックトラッキングや追加のパス記録は不要です。
二分探索木の最小共通祖先アルゴリズムの手順
- ルートから始めて、current = rootとする。
- p.valとq.valの両方がcurrent.valより小さい場合、左に移動します。
- 両方ともcurrent.valより大きい場合は、右に移動します。
- それ以外の場合は、現在のノードが分岐点となり、現在のノードが返されます。
二分探索木の最小共通祖先:複雑性分析
| プロジェクト | 複雑 |
|---|---|
| 時間計算量 | おお) |
| 空間の複雑さ | ○(1) |
各ステップは1レベルずつ下に移動し、時間計算量は木の高さに等しいO(h)、バランスが取れている場合はO(log n)となります。反復バージョンはスタッキングを必要とせず、空間計算量はO(1)です。再帰バージョンの空間計算量はO(h)です。
二分探索木の最小共通祖先の境界ケースと一般的なエラー
- pまたはqが別のノードの祖先である場合、答えはその祖先ノードになります。
- この問題では、両方のノードがツリー内に存在することが保証されています。存在しない場合は、追加の検証が必要です。
- この解決策は二分探索木(BST)にのみ有効です。一般的な二分木の場合は、後順再帰バージョンが必要です。
- 通常のツリーを用いた一般的な解法は、二分探索木の順序性を損なうため使用しないでください。
二分探索木の最小共通祖先;他の解法との比較
| 解法 | 時間 | 空間 | 例示する |
|---|---|---|---|
| ルートからノードまでの2つのパスを記録し、それらを比較してください。 | おお) | おお) | 汎用性はあるものの、追加のパス保存容量が必要となる。 |
| 一般二分木の後順再帰解法 | の上) | おお) | その通りですが、BSTの特性は活用されていません。 |
| BSTプロパティを使用した反復ダウンリンク | おお) | ○(1) | この記事では |
