Dado un árbol binario, el problema es encontrar el espejo de un Node dado. El espejo de un Node es un Node que existe en la posición del espejo del Node en el subárbol opuesto en la raíz.
Ejemplos:
C++
// C++ program to find the mirror Node
// in Binary tree
#include <bits/stdc++.h>
using namespace std;
/* A binary tree Node has data,
pointer to left child and
a pointer to right child */
struct Node
{
int key;
struct Node* left, *right;
};
// create new Node and initialize it
struct Node* newNode(int key)
{
struct Node* n = (struct Node*)
malloc(sizeof(struct Node*));
if (n != NULL)
{
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
else
{
cout << "Memory allocation failed!"
<< endl;
exit(1);
}
}
// recursive function to find mirror of Node
int findMirrorRec(int target, struct Node* left,
struct Node* right)
{
/* if any of the Node is none then Node itself
and decendent have no mirror, so return
none, no need to further explore! */
if (left == NULL || right == NULL)
return 0;
/* if left Node is target Node, then return
right's key (that is mirror) and vice
versa */
if (left->key == target)
return right->key;
if (right->key == target)
return left->key;
// first recur external Nodes
int mirror_val = findMirrorRec(target,
left->left,
right->right);
if (mirror_val)
return mirror_val;
// if no mirror found, recur internal Nodes
findMirrorRec(target, left->right, right->left);
}
// interface for mirror search
int findMirror(struct Node* root, int target)
{
if (root == NULL)
return 0;
if (root->key == target)
return target;
return findMirrorRec(target, root->left,
root->right);
}
// Driver Code
int main()
{
struct Node* root = newNode(1);
root-> left = newNode(2);
root->left->left = newNode(4);
root->left->left->right = newNode(7);
root->right = newNode(3);
root->right->left = newNode(5);
root->right->right = newNode(6);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
// target Node whose mirror have to be searched
int target = root->left->left->key;
int mirror = findMirror(root, target);
if (mirror)
cout << "Mirror of Node " << target
<< " is Node " << mirror << endl;
else
cout << "Mirror of Node " << target
<< " is NULL! " << endl;
}
// This code is contributed by SHUBHAMSINGH10
C
// C program to find the mirror Node in Binary tree
#include <stdio.h>
#include <stdlib.h>
/* A binary tree Node has data, pointer to left child
and a pointer to right child */
struct Node
{
int key;
struct Node* left, *right;
};
// create new Node and initialize it
struct Node* newNode(int key)
{
struct Node* n = (struct Node*)
malloc(sizeof(struct Node*));
if (n != NULL)
{
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
else
{
printf("Memory allocation failed!");
exit(1);
}
}
// recursive function to find mirror of Node
int findMirrorRec(int target, struct Node* left,
struct Node* right)
{
/* if any of the Node is none then Node itself
and decendent have no mirror, so return
none, no need to further explore! */
if (left==NULL || right==NULL)
return 0;
/* if left Node is target Node, then return
right's key (that is mirror) and vice
versa */
if (left->key == target)
return right->key;
if (right->key == target)
return left->key;
// first recur external Nodes
int mirror_val = findMirrorRec(target,
left->left,
right->right);
if (mirror_val)
return mirror_val;
// if no mirror found, recur internal Nodes
findMirrorRec(target, left->right, right->left);
}
// interface for mirror search
int findMirror(struct Node* root, int target)
{
if (root == NULL)
return 0;
if (root->key == target)
return target;
return findMirrorRec(target, root->left, root->right);
}
// Driver
int main()
{
struct Node* root = newNode(1);
root-> left = newNode(2);
root->left->left = newNode(4);
root->left->left->right = newNode(7);
root->right = newNode(3);
root->right->left = newNode(5);
root->right->right = newNode(6);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
// target Node whose mirror have to be searched
int target = root->left->left->key;
int mirror = findMirror(root, target);
if (mirror)
printf("Mirror of Node %d is Node %d\n",
target, mirror);
else
printf("Mirror of Node %d is NULL!\n", target);
}
Java
// Java program to find the mirror Node in Binary tree
class GfG {
/* A binary tree Node has data, pointer to left child
and a pointer to right child */
static class Node
{
int key;
Node left, right;
}
// create new Node and initialize it
static Node newNode(int key)
{
Node n = new Node();
n.key = key;
n.left = null;
n.right = null;
return n;
}
// recursive function to find mirror of Node
static int findMirrorRec(int target, Node left, Node right)
{
/* if any of the Node is none then Node itself
and decendent have no mirror, so return
none, no need to further explore! */
if (left==null || right==null)
return 0;
/* if left Node is target Node, then return
right's key (that is mirror) and vice
versa */
if (left.key == target)
return right.key;
if (right.key == target)
return left.key;
// first recur external Nodes
int mirror_val = findMirrorRec(target, left.left, right.right);
if (mirror_val != 0)
return mirror_val;
// if no mirror found, recur internal Nodes
return findMirrorRec(target, left.right, right.left);
}
// interface for mirror search
static int findMirror(Node root, int target)
{
if (root == null)
return 0;
if (root.key == target)
return target;
return findMirrorRec(target, root.left, root.right);
}
// Driver
public static void main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.left.right = newNode(7);
root.right = newNode(3);
root.right.left = newNode(5);
root.right.right = newNode(6);
root.right.left.left = newNode(8);
root.right.left.right = newNode(9);
// target Node whose mirror have to be searched
int target = root.left.left.key;
int mirror = findMirror(root, target);
if (mirror != 0)
System.out.println("Mirror of Node " + target + " is Node " + mirror);
else
System.out.println("Mirror of Node " + target + " is null ");
}
}
Python3
# Python3 program to find the mirror node in
# Binary tree
class Node:
'''A binary tree node has data, reference to left child
and a reference to right child '''
def __init__(self, key, lchild=None, rchild=None):
self.key = key
self.lchild = None
self.rchild = None
# recursive function to find mirror
def findMirrorRec(target, left, right):
# If any of the node is none then node itself
# and decendent have no mirror, so return
# none, no need to further explore!
if left == None or right == None:
return None
# if left node is target node, then return
# right's key (that is mirror) and vice versa
if left.key == target:
return right.key
if right.key == target:
return left.key
# first recur external nodes
mirror_val = findMirrorRec(target, left.lchild, right.rchild)
if mirror_val != None:
return mirror_val
# if no mirror found, recur internal nodes
findMirrorRec(target, left.rchild, right.lchild)
# interface for mirror search
def findMirror(root, target):
if root == None:
return None
if root.key == target:
return target
return findMirrorRec(target, root.lchild, root.rchild)
# Driver
def main():
root = Node(1)
n1 = Node(2)
n2 = Node(3)
root.lchild = n1
root.rchild = n2
n3 = Node(4)
n4 = Node(5)
n5 = Node(6)
n1.lchild = n3
n2.lchild = n4
n2.rchild = n5
n6 = Node(7)
n7 = Node(8)
n8 = Node(9)
n3.rchild = n6
n4.lchild = n7
n4.rchild = n8
# target node whose mirror have to be searched
target = n3.key
mirror = findMirror(root, target)
print("Mirror of node {} is node {}".format(target, mirror))
if __name__ == '__main__':
main()
C#
// C# program to find the
// mirror Node in Binary tree
using System;
class GfG
{
/* A binary tree Node has data,
pointer to left child and a
pointer to right child */
class Node
{
public int key;
public Node left, right;
}
// create new Node and initialize it
static Node newNode(int key)
{
Node n = new Node();
n.key = key;
n.left = null;
n.right = null;
return n;
}
// recursive function to find mirror of Node
static int findMirrorRec(int target, Node left,
Node right)
{
/* if any of the Node is none then Node itself
and decendent have no mirror, so return
none, no need to further explore! */
if (left==null || right==null)
return 0;
/* if left Node is target Node, then return
right's key (that is mirror) and vice
versa */
if (left.key == target)
return right.key;
if (right.key == target)
return left.key;
// first recur external Nodes
int mirror_val = findMirrorRec(target,
left.left, right.right);
if (mirror_val != 0)
return mirror_val;
// if no mirror found, recur internal Nodes
return findMirrorRec(target,
left.right, right.left);
}
// interface for mirror search
static int findMirror(Node root, int target)
{
if (root == null)
return 0;
if (root.key == target)
return target;
return findMirrorRec(target,
root.left, root.right);
}
// Driver code
public static void Main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.left.right = newNode(7);
root.right = newNode(3);
root.right.left = newNode(5);
root.right.right = newNode(6);
root.right.left.left = newNode(8);
root.right.left.right = newNode(9);
// target Node whose mirror have to be searched
int target = root.left.left.key;
int mirror = findMirror(root, target);
if (mirror != 0)
Console.WriteLine("Mirror of Node " +
target + " is Node " +
mirror);
else
Console.WriteLine("Mirror of Node " + target +
" is null ");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the mirror
// Node in Binary tree
/* A binary tree Node has data, pointer
to left child and a pointer to right child */
class Node
{
// Create new Node and initialize it
constructor(key)
{
this.key = key;
this.left = this.right = null;
}
}
// Recursive function to find mirror of Node
function findMirrorRec(target, left, right)
{
/* If any of the Node is none then Node itself
and decendent have no mirror, so return
none, no need to further explore! */
if (left == null || right == null)
return 0;
/* If left Node is target Node, then return
right's key (that is mirror) and vice
versa */
if (left.key == target)
return right.key;
if (right.key == target)
return left.key;
// First recur external Nodes
let mirror_val = findMirrorRec(
target, left.left, right.right);
if (mirror_val != 0)
return mirror_val;
// If no mirror found, recur internal Nodes
return findMirrorRec(target, left.right,
right.left);
}
// Interface for mirror search
function findMirror(root, target)
{
if (root == null)
return 0;
if (root.key == target)
return target;
return findMirrorRec(target, root.left,
root.right);
}
// Driver code
let root = new Node(1);
root.left = new Node(2);
root.left.left = new Node(4);
root.left.left.right = new Node(7);
root.right = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(8);
root.right.left.right = new Node(9);
// Target Node whose mirror have to be searched
let target = root.left.left.key;
let mirror = findMirror(root, target);
if (mirror != 0)
document.write("Mirror of Node " + target +
" is Node " + mirror + "<br>");
else
document.write("Mirror of Node " + target +
" is null " + "<br>");
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA