如何在二叉树中找到给定节点（或项目）的镜像节点高效地

我一直在考虑这个问题，并且我还没有找到一个好的，有效的解决方案。如何在二叉树中找到给定节点（或项目）的镜像节点高效地

如何查找二叉树中给定节点（或项目）的镜像节点？

// 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.

感谢。

来源

2010-07-04 Peter Lee

这可能是一个愚蠢的问题，但你能解释一个镜像节点是什么或至少链接到它的定义？ – 2010-07-04 19:23:58

嗨马克，是的，对，它可能是一个愚蠢的问题，但它也可能是更好地理解二叉树的好习惯:-)谢谢。我添加了镜像节点定义的示例。 – 2010-07-04 19:44:55

我已经为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); 
}

来源

2010-07-04 21:37:46 Kru

嗨克里斯，您的解决方案很漂亮，复杂度为O（n）。（我不认为我们可以有更快的解决方案:-) – 2010-07-05 05:39:32

@Peter：如果树被排序，你会用类似的算法来实现O（log n），递归地选择正确的路径。 – Kru 2010-07-06 14:26:49

感谢克里斯的美丽的解决方案。有效。

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

来源

2010-07-05 05:37:36

如何在二叉树中找到给定节点（或项目）的镜像节点高效地

回答

相关问题