algorithm - 关于树数据结构的问题: How can we fill all inorder successor pointer of all tree nodes?

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*注意:* A 的顺序后继者是 F、C 和 G。

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

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

情况 1) 一些 Successor 指针可能是 NULL 。在这种情况下，您必须用直接的 Inorder Successor 填充该指针。

示例:如果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;
}