ツリーデータ構造に関する質問：すべてのツリーノードのすべてのインオーダー後続ポインタをどのように埋めることができますか？

Question

ツリーノードには、left、* right、および* Successorの3つのポインタが含まれています。

Struct node{ 
    int data; 
    struct node *left; 
    struct node *right; 
    struct node *successor; 
}; 


     A 
    /\ 
     B C 
    /\/\ 
    D E F G 

INORDERのトラバーサル：DBEAFCG * 注：は*後継INORDER A F、C及びG.

**Function prototype:** void FillSuccessorNodes(struct node *root); 

ツリーのルートノードが私たちに与えられていると我々は後継ポインタを記入する必要がありますすべてのノードについて。

ケース1）後継ポインタの一部はNULLです。この場合、直後のInorder Successorでそのポインタを埋める必要があります。

例：後継ポインタのA->後継== nullの場合、F =

ケース2 A->後継を埋める）、いくつかは既に後継を補正する点もよいです。この場合、後続ポインタを変更する必要はありません。

例：1）A->後継= Fが有効である

 2) A->successor = C is valid 

    3) A-successor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes. 

ケース3）後継ポインタのいくつかはある NULLが、後継者をINVALIDに指してこれらのポインタは、それが後継INORDER可能性がすなわちありませんかいくつかのゴミ値。この場合、これらのノードに直後の後続ノードを入力する必要があります。

例：インタビュアーが私にO（n）の時間複雑で時間効率的なソリューションを求めて

 1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F. 

    2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F. 

1）。余分なスペースが許されます。 2）彼女はヒントを与えました。つまり、ハッシュを使用することができます。

この問題の解決方法が分かっている場合は、お知らせください。

Answer 1

質問とヒントが私に誤解を招くようです。いずれにしても、後続ノードが無効であるかどうかをチェックするためには、すべてのノードをチェックする必要があるため、無効な手段を知るために後継ノードを計算する必要があるため、標準的なO（n）トラバーサルを使用することもできます。

Answer 2

inorder traversalを少し変更するだけで、前身を覚えておき、predecessot-> successor = currentと設定する必要があります。

stack<node*> s; 
node* t = root ,*pred=NULL; 
while(true) 
{ 
    if(t){ 
      s.push(t); 
      t= t->left; 
      continue; 
    }   
    if(s.empty()) { break;} 
    t= s.top(); 
    if(NULL != pred && pred->succesor != t) 
    { 
     pred->succesor = t;  
    } 
    pred = t; 
    s.pop();   
    cout<<t->c; 
    t= t->right; 
}