Как найти зеркальный узел заданного узла (или элемента) в двоичном дереве эффективно

Question

Я думал об этой проблеме, и я не нашел эффективного и эффективного решения.

Как найти зеркальный узел заданного узла (или элемента) в двоичном дереве?

// Node definition 
struct _Node { 
    char data; 
    struct _Node* left; 
    struct _Node* right; 
} Node; 

// Assumption: 
//  "given" is guaranteed in the binary tree ("root" which is not NULL) 
Node* FindMirrorNode(Node* root, Node* given) 
{ 
    // Implementation here 
} 

// OR: 

// Assumption: 
// in the binary tree ("root"), there is no repeated items, which mean in each node the char data is unique; 
// The char "given" is guaranteed in the binary tree. 
char FindMirrorNodeData(Node* root, char given) 
{ 
    // Implementation here 
} 

Примечание: Я не спрашиваю о том, как найти зеркальное дерево данного дерева :-)

For example, considering the tree below 
       A 
     / \ 
     B    C 
    /  / \ 
    D    E  F 
    \   /\ 
     G   H I 

The mirror node of 'D' is node 'F'; while the mirror node of 'G' is NULL. 

Спасибо.

Answer 1

Я написал решение для функции с char. Есть FindMirrorNode(r, n) == FindMirrorNodeData(r, n->data)?

Вы должны пройти через все дерево, просматривая данные, сохраняя зеркальные узлы в стеке. Это довольно простое решение, которое все еще достаточно эффективно. Если вы хотите, вы можете преобразовать tail-calls в while.

static Node* FindMirrorNodeRec(char given, Node* left, Node* right) 
{ 
    // if either node is NULL then there is no mirror node 
    if (left == NULL || right == NULL) 
     return NULL; 
    // check the current candidates 
    if (given == left->data) 
     return right; 
    if (given == right->data) 
     return left; 
    // try recursively 
    // (first external then internal nodes) 
    Node* res = FindMirrorNodeRec(given, left->left, right->right); 
    if (res != NULL) 
     return res; 
    return FindMirrorNodeRec(given, left->right, right->left); 
} 

Node* FindMirrorNodeData(Node* root, char given) 
{ 
    if (root == NULL) 
     return NULL; 
    if (given == root->data) 
     return root; 
    // call the search function 
    return FindMirrorNodeRec(given, root->left, root->right); 
} 

Answer 2

Спасибо за красивое решение Криса. Это сработало.

Node* FindMirrorNodeRec(Node* given, Node* left, Node* right) 
{ 
    // There is no mirror node if either node is NULL 
    if (!left || !right) 
     return NULL; 

    // Check the left and right 
    if (given == left) 
     return right; 
    if (given == right) 
     return left; 

    // Try recursively (first external and then internal) 
    Node* mir = FindMirrorNodeRec(given, left->left, right->right); 
    if (mir) 
     return mir; 

    // Internally 
    return FindMirrorNodeRec(given, left->right, right->left); 
} 

// Find the mirror node of the given node 
// Assumption: root is not NULL, and the given node is guaranteed 
//    in the tree (of course, not NULL :-) 
Node* FindMirrorNode(Node* const root, Node* const given) 
{ 
    if (!root || root == given) 
     return root; 

    return FindMirrorNodeRec(given, root->left, root->right); 
}