이진 트리에서 주어진 노드 (또는 항목)의 미러 노드를 효율적으로 찾는 방법

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)입니까?

스택에 미러 노드를 유지하면서 주어진 데이터를 검색하는 전체 트리를 탐색해야합니다. 꽤 간단한 솔루션이지만 여전히 효율적입니다. 꼬리 전화를 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); 
}