0

二分探索ツリー内のノードのペアの最小共通祖先を見つけるためのプログラムを書いていました(要素がツリーに存在する場合)。私のロジックは：

  1. ルートから開始します。
  2. 両方の要素が現在の要素よりも大きい場合は、ルートを返します (ここが違います)。
  3. 両方ともルートより小さい場合は、左側のサブツリーで再帰します。
  4. それ以外の場合はルートを返します（一方が小さいほど他方が大きい）。

ただし、オンラインで見つかったアルゴリズム ( http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html ) はステップ 2 を変更します。この場合、アルゴリズムは右のサブツリーで再帰するため、次のツリーの場合:

  2
 / \
1   4
   / \
  3   5

3 と 5 を入力すると、私のアルゴリズムは 2 になり、他のアルゴリズムは出力として 4 になります。

それで、LCAの定義が間違っていることを理解しているのですか（「2は4より低く、共通の祖先であるため）、それとも私のアルゴリズムは正しいですか？」

4

1 に答える 1

1

T の v と w の LCA は、ルートから最も離れた v と w の共有先祖です。したがって、オンライン版はあなたの理解とは異なる正しいものです。

このLCA定義をチェックしてください

また、必要に応じて再帰を回避することもできます。候補からルート ノードまでのルートをトレースするだけです。最初の共通ノードは LCA です

于 2013-06-19T04:52:23.480 に答える