ノード w がツリー内のノード u とノード v の間のパス上にあるかどうかを判断する必要がある問題を解決しようとしています (必ずしもバイナリではありません)。
たとえば、次のツリーの場合:
1
2 3
4 5 6 7
ノード 2 は、ノード 4 から 7 へのパス上にあります。
明らかな解決策は、ツリーのオイラー ツアーを取得し、両方のノードの最初の発生の間にアクセスされたノードをトラバースすることです。ただし、n がツリー内のノード数である最悪の場合、これは O(n) ソリューションになります。これは LCA (Lowest Common Ancestor) を使用して実行できることをどこかで読みました。しかし、私はその方法を理解できないようです。誰かが私にアドバイスしてもらえますか？