バイナリツリーで特定のノード(またはアイテム)のミラーノードを効率的に見つける方法
-
02-10-2019 - |
質問
私はこの問題を考えてきましたが、良い、効率的な解決策を見つけていません。
バイナリツリーで特定のノード(またはアイテム)のミラーノードを見つける方法は?
// 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.
ありがとう。
解決
機能の解決策を書きました 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);
}
他のヒント
クリスの美しいソリューションをありがとう。機能した。
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);
}
所属していません StackOverflow