二分探索木の最小共通祖先:解法チュートリアル - 3つの解法の完全比較 | LeetCode 235 ベストプラクティス

二分探索木の最小共通祖先:問題解決チュートリアル図 | LeetCode 235

この記事では、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 != q
  • p そして q BST に存在します。

パイソン

				
					# バイナリ ツリー ノードの定義。 # クラス 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 を返します
				
			

二分探索木の最小共通祖先:解法

二分探索木(BST)の順序性を利用することで、この問題は簡略化できます。両方の目標値が現在のノードより小さい場合、答えは左部分木に存在し、両方が大きい場合は右部分木に存在します。また、「一方が他方より小さい」または「どちらか一方が現在のノードと等しい」場合は、現在のノードが最小共通祖先となります。バックトラッキングや追加のパス記録は不要です。

二分探索木の最小共通祖先アルゴリズムの手順

  1. ルートから始めて、current = rootとする。
  2. p.valとq.valの両方がcurrent.valより小さい場合、左に移動します。
  3. 両方ともcurrent.valより大きい場合は、右に移動します。
  4. それ以外の場合は、現在のノードが分岐点となり、現在のノードが返されます。

二分探索木の最小共通祖先:複雑性分析

プロジェクト複雑
時間計算量おお)
空間の複雑さ○(1)

各ステップは1レベルずつ下に移動し、時間計算量は木の高さに等しいO(h)、バランスが取れている場合はO(log n)となります。反復バージョンはスタッキングを必要とせず、空間計算量はO(1)です。再帰バージョンの空間計算量はO(h)です。

二分探索木の最小共通祖先の境界ケースと一般的なエラー

  • pまたはqが別のノードの祖先である場合、答えはその祖先ノードになります。
  • この問題では、両方のノードがツリー内に存在することが保証されています。存在しない場合は、追加の検証が必要です。
  • この解決策は二分探索木(BST)にのみ有効です。一般的な二分木の場合は、後順再帰バージョンが必要です。
  • 通常のツリーを用いた一般的な解法は、二分探索木の順序性を損なうため使用しないでください。

二分探索木の最小共通祖先;他の解法との比較

解法時間空間例示する
ルートからノードまでの2つのパスを記録し、それらを比較してください。おお)おお)汎用性はあるものの、追加のパス保存容量が必要となる。
一般二分木の後順再帰解法の上)おお)その通りですが、BSTの特性は活用されていません。
BSTプロパティを使用した反復ダウンリンクおお)○(1)この記事では