class TreeNode {
TreeNode parent;
TreeNode left;
TreeNode right;
// other data fields omitted - not relevant
}
pとの2 つのノードが与えられqた場合、どのようにして最も低い共通の祖先を見つけますか? (両方とも非常に大きなツリーに属していると仮定します)
ツリーのルートへの参照がありません。
これを行う最も効率的な方法は何ですか? これまでのところ、私が持っている唯一のアイデアは
(1) ノード p を選択します (どちらでも構いません)
(2) p の左部分木を検索し、q がある場合は p を返す
(3) そうでなければ、p の右側の部分木を検索し、q がある場合は p を返す
(4) そうでない場合は、1 レベル親に移動し、p を含まないサブツリーを検索します。q が見つかった場合は、親を返します。
(5) そうでない場合は、もう一度 1 レベル上に移動し、(4) を繰り返します (この親を含まないサブツリーを検索します)
これは非常に非効率に思えます。より良いアルゴリズムはありますか？