树数据结构问题：如何填充所有树节点的所有中序后继指针？

Question

树节点包含 3 个指针 *left、*right 和 *Successor 。

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


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

INORDER 遍历：DBEAFCG *注意：* 中序后继者是 F、C 和 G。

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

树的根节点给我们，我们需要为所有节点填充后继者指针。

情况 1) 某些后继指针可能为 NULL 。在这种情况下，您必须用立即顺序后继者填充该指针。

示例：如果 A->Successor == NULL，则填充 A->Successor = F

情况 2) 某些 Successor 指针可能已经指向正确的后继者。这种情况下你不需要修改后继指针。

示例： 1) A->successor = 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，但这些指针指向无效后继，即它可能是有序后继或某些垃圾值。在这种情况下，您必须用直接后继节点填充这些节点。

示例：

     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) 面试官问我时间复杂度为 O(n) 的高效解决方案。允许额外的空间。 2）她给出了一些提示，即我们可以使用哈希。

如果您知道这个问题的解决方案，请告诉我。

Answer 1

这个问题和提示似乎误导了我。由于无论如何您都必须检查所有节点以检查它们的后继节点是否无效，并且由于您必须计算后继节点以了解无效的含义，因此您不妨使用标准的 O(n) 中序遍历，例如：

#include <utility>
using namespace std;

typedef pair<node*, node*> node_pair;

node_pair setInOrderSuccessors(node* root)
{
    node_pair result(root, root);

    if (root->left) {
        const node_pair pair = setInOrderSuccessors(root->left);
        result.first = pair.first;
        pair.second->successor = root;
    }

    if (root->right) {
        const node_pair pair = setInOrderSuccessors(root->right);
        result.second = pair.second;
        root->successor = pair.first;
    }

    return result;
}

void  FillSuccessorNodes(node *root)
{
    const node_pair pair = setInOrderSuccessors(root);
    pair.second->successor = 0;
}

Answer 2

只需要对中序遍历稍作修改，记住前驱并设置前驱->后继=当前即可。

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; 
}