ツリー内の2つのノードの最も近い共通の親ノードを探します

7294 ワード
vector 面接試験 tree null Path 連想する
ツリー内の2つのノードの最も近い共通の親ノードを探します
いろいろな面接でよく見られる質問ですhttp://fayaa.com/tiku/view/16/ここにはいいまとめがあります.
ツリー内の2つのノードの共通の親ノードで最も近いノードを探します.
ケース1.ノードはleft/rightのみでparentポインタがなくrootは既知
ケース2.rootは不明ですが、ノードごとにparentポインタがあります.
ケース3.ツリーはツリーであり、rootと2つのノードの値(a,b)は既知である
--------------------------------------------------------------------------------
状況1は1つ目の状況ですが、複雑に見えますが、最後に2つ目の状況から話しましょう.
                                            10
                                         /      \                                        6         14                                      /   \      /　 \                                   4      8   12 　 16
                                  / \
                                 3   5
例として二叉木を描く.3と8の2つのノードの共通の親ノードを探す場合は、まず3からルートノードへの道の力を見つけ、8からルートノードへの経路を見つけることです.
                                            10
                                         /     \                                        6         14                                      /  \      /　\                                   4      8   12 　 16
                                 / \
                                 3   5
3の経路は赤で、8のは緑で、ここの問題は実際にはもう一つの私たちがよく知っている問題で、2つの交差する単鎖表があって、それらの交差点を探し出すことができます!
この二叉木の画像を逆さに見たり、首を逆さに見たりすればわかる:)その方法も伝統的にlinkedList Aの長さlengthA、linkedList Bの長さLengthBを求める.そして長いチェーンテーブルをabs(lengthA-lengthB)ステップで歩かせた後、並んで進むと解決します.
  
 int getLength (bstNode* pNode)   
 {      
     int length = 0;   
     bstNode* pTemp = pNode;   
     while (pTemp)   
     {   
         length ++ ;   
         pTemp = pTemp->pParent;   
     }   
     return length;   
 }   
 bstNode* findLCACase2(bstNode* pNode1, bstNode* pNode2)   
 {   
     int length1 = getLength(pNode1);   
     int length2 = getLength(pNode2);   
        
     // skip the abs(length1-length2)   
     bstNode* pIter1 = NULL;   
     bstNode* pIter2 = NULL;   
     int k=0;   
     if (length1>=length2)   
     {   
         bstNode* pTemp = pNode1;   
         while (k++<length1-length2)   
         {   
             pTemp = pTemp->pParent;    
         }   
         pIter1 = pTemp;   
         pIter2 = pNode2;   
     }   
     else  
     {   
         bstNode* pTemp = pNode1;   
         while (k++<length2-length1)   
         {   
             pTemp = pTemp->pParent;    
         }   
         pIter1 = pNode1;   
         pIter2 = pTemp;   
     }   
        
     while (pIter1&&pIter2&&pIter1!= pIter2)   
     {   
         pIter1 = pIter1->pParent;   
         pIter2 = pIter2->pParent;   
     }   
     return pIter1;   
 }

 
自分でコードを書いて、なんだかダラダラしていて、縁のある人が文章を見てから書き直してくれることを望んでいます.
やはりもとのこの図で、情況の3、もし2叉の捜索の木ならば、しかもrootとa,bは既知で、私達のこのcaseはa,b=3,8を仮定します.この条件を知ってから、私たちは自然に再帰(もちろん再帰しなくてもいい)を連想して下を探します.肝心なのは収束条件であり,当然検査されたこのノードが最近の父親ノードであると判断できるのはどんな場合であるか.実はこの例からいくつかの端緒が見えて、もし現在アクセスしているノードがa,bよりも小さいならば、きっとだめです.a,bより大きくてもだめです.すなわち,このノードはa<=node<=bの区間内でのみ成立する(abstNode* findLCACase3(bstNode* pNode, int value1, int value2) { bstNode* pTemp = pNode; while (pTemp) { if (pTemp->data>value1 && pTemp->data>value2) pTemp = pTemp->pLeft; else if(pTemp->data<value1 && pTemp->data<value2) pTemp = pTemp->pRight; else return pTemp; } return NULL; } bstNode* findLCACase3(bstNode* pNode, int value1, int value2) { bstNode* pTemp = pNode; while (pTemp) { if (pTemp->data>value1 && pTemp->data>value2) pTemp = pTemp->pLeft; else if(pTemp->data<value1 && pTemp->data<value2) pTemp = pTemp->pRight; else return pTemp; } return NULL; }
はい、前の問題はすべて解決しました.私たちは振り返って最初の状況を見てみましょう.ROOTとleft、rightノードだけで、parentもソートツリーではありません.どうしますか.ネット上でも多くのいわゆるLCA、RMQアルゴリズムが伝わっていて、私たちは最も適切なものを探す暇がありません.特に面接の時、特定の時間空間の下で論理的に非常に複雑なものを書くのは難しいです(例えば、面接の時にSuffix Treeを実現するか、動的計画で最も長い公共のサブストリングを求めるか、効率が違っても、私は動的計画を選択します:).そこで、似たような問題に遭遇したとき、私は簡単な記録を選んでnode 1とnode 2の経路を見つけて、それからそれらの経路を似たような状況2で分析します.例えば、node 1=3、node 2=8というcaseです.私たちはルートノードから3というノードを見つけることができます.同時に、経路3,4,6,10を記録して、似たような私たちも8,6,10を見つけることができます.このような情報を2つのvectorに格納し,長いvectorから始まる余分なノード3を捨て,同じ残りの長さから比較し,4!=8,6==6、coooool、私たちは私たちの答えを見つけました.次のコードは完全にこの考え方に従って書かれています.
#include <vector>   
 bool nodePath (bstNode* pRoot, int value, std::vector<bstNode*>& path)   
 {   
     if (pRoot==NULL) return false;   
     if (pRoot->data!=value)   
     {   
         if (nodePath(pRoot->pLeft,value,path))   
         {   
             path.push_back(pRoot);   
             return true;   
         }   
         else  
         {   
             if (nodePath(pRoot->pRight,value,path))   
             {   
                 path.push_back(pRoot);   
                 return true;   
             }   
             else  
                 return false;   
         }   
     }   
     else  
     {   
         path.push_back(pRoot);   
         return true;   
     }   
 }   
 bstNode* findLCACase1(bstNode* pNode, int value1, int value2)   
 {   
     std::vector<bstNode*> path1;   
     std::vector<bstNode*> path2;   
     bool find = false;   
     find |= nodePath(pNode, value1, path1);   
     find &= nodePath(pNode, value2, path2);   
     bstNode* pReturn=NULL;   
     if (find)   
     {   
         int minSize = path1.size()>path2.size()?path2.size():path1.size();   
         int it1 = path1.size()-minSize;   
         int it2 = path2.size()-minSize;   
         for (;it1<path1.size(),it2<path2.size();it1++,it2++)   
         {   
             if (path1[it1]==path2[it2])   
             {   
                 pReturn = path1[it1];   
                 break;   
             }   
         }   
     }   
     return pReturn;   
 }  
 #include <vector>
 bool nodePath (bstNode* pRoot, int value, std::vector<bstNode*>& path)
 {
  if (pRoot==NULL) return false;
  if (pRoot->data!=value)
  {
   if (nodePath(pRoot->pLeft,value,path))
   {
    path.push_back(pRoot);
    return true;
   }
   else
   {
    if (nodePath(pRoot->pRight,value,path))
    {
     path.push_back(pRoot);
     return true;
    }
    else
     return false;
   }
  }
  else
  {
   path.push_back(pRoot);
   return true;
  }
 }
 bstNode* findLCACase1(bstNode* pNode, int value1, int value2)
 {
  std::vector<bstNode*> path1;
  std::vector<bstNode*> path2;
  bool find = false;
  find |= nodePath(pNode, value1, path1);
  find &= nodePath(pNode, value2, path2);
  bstNode* pReturn=NULL;
  if (find)
  {
   int minSize = path1.size()>path2.size()?path2.size():path1.size();
   int it1 = path1.size()-minSize;
   int it2 = path2.size()-minSize;
   for (;it1<path1.size(),it2<path2.size();it1++,it2++)
   {
    if (path1[it1]==path2[it2])
    {
     pReturn = path1[it1];
     break;
    }
   }
  }
  return pReturn;
 }

参照先:http://blog.csdn.net/yangkele/article/details/6399707
JAvaパッケージprivateメンバー変数setterとgetterメソッドテスト
メールフォームテンプレート