ルートを参照することなく、2つのツリーノードの共通の祖先を見つけますか？

Question

class TreeNode { 
    TreeNode parent; 
    TreeNode left; 
    TreeNode right; 

    // other data fields omitted - not relevant 
} 

pとqの2つのノードが指定されていますが、最も低い共通祖先はどのようにして見つけられますか？ （両方が非常に大きな木に属していると仮定してください）

あなたはツリーのルートを参照していません。

これを行う最も効率的な方法は何ですか？ はこれまでのところ、私が持っている唯一のアイデアは

（1）ノードp（これは関係ありません）

（2）のqを見れば、Pの左サブツリーを検索し、リターンP

を選ぶ

にしました

親に1つのレベルに行くとq見つかった場合 は、Pが含まれていないサブツリーを検索し、Qを見た場合（3）他に、Pの右側のサブツリーを検索し、リターンP

（4）他、返品親

（5） （4）（ にはこの親が含まれていないサブツリーを検索してください）

これは非常に効率が悪いようです。任意のより良いアルゴリズムですか？

Answer 1

使用できるRAMの量に極端な制限はありますか？そうでない場合は、次のような提案をします。

visited_nodes = {} // something like a HashMap, with O(1) insert and retrieval 
node1 = p 
node2 = q 

while True: 
    if node1 == null and node2 == null: // the nodes don't seem to be in same tree 
     return null // or failure or anything like that 

    if node1 is not null: 
     if node1 in visited_nodes: // node1 must be lowest common ancestor 
      return node1 
     else: 
      visited_nodes.insert(node1) // remember that we've seen this node 
      node1 = node1.getParent() 

    if node2 is not null: 
     if node2 in visited_nodes: // node2 must be lowest common ancestor 
      return node2 
     else: 
      visited_nodes.insert(node2) // remember that we've seen this node 
      node2 = node2.getParent() 

直感的な考えは次のとおりです。我々は両方のノードで同時に始める。ループの各反復では、両方のノードから1ステップアップします。ノードが見つかるたびに、マップに（O（1）の挿入と検索/チェックが必要です）マップに配置します。すでにマップに入れているノードに出会ったら、それが私たちのソリューションでなければなりません。

このコードはd_pとd_qはpとqは、それぞれ、であることをツリー内の深さレベルを表す以上max(d_p, d_q)反復のため実行することはありません。これは特に、両方のノードがルートにかなり接近している場合に大きな利点になります。また、コードが無限のツリーに対しても機能することを意味します（ただし、ソリューションは無限ループに陥る）。