如何在二叉樹中找到給定節點（或項目）的鏡像節點高效地

我一直在考慮這個問題，並且我還沒有找到一個好的，有效的解決方案。如何在二叉樹中找到給定節點（或項目）的鏡像節點高效地

如何查找二叉樹中給定節點（或項目）的鏡像節點？

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

如何在二叉樹中找到給定節點（或項目）的鏡像節點高效地

回答

相關問題