Dados dos árboles binarios con la misma estructura pero que pueden tener diferente disposición de valor y dado un número entero K . La tarea es verificar que después de exactamente el intercambio de K en el primer árbol, se convertirá en un espejo del segundo. En un intercambio, tomamos dos Nodes del mismo padre e intercambiamos su subárbol izquierdo y derecho.
Ejemplos:
Entrada: K = 1
1 1
/ \ / \
2 3 2 3
Salida: SíEntrada: K = 4
11 11
/ \ / \
25 15 25 15
/ \ / \ / \ / \
7 9 10 21 10 21 9 7
Salida: Sí
Explicación: Aquí primero necesitamos intercambiar dos pares (25, 15) y (10, 21) en el primer árbol, por lo tanto, K = 2. Y luego intercambiamos (21, 7) y (10, 9), por lo tanto, aquí hay un total de 4 intercambios.
Enfoque: El enfoque básico para resolver este problema es usar la recursividad y la pila según la siguiente idea:
La idea es atravesar el primer árbol y verificar intercambiando Nodes recursivamente , si el árbol se convierte en una imagen especular del segundo árbol.
Siga los pasos a continuación para implementar el enfoque anterior:
- Verifique todos los Nodes respectivos de ambos árboles uno por uno con la ayuda del recorrido iterativo en orden .
- Si se encuentra que las partes de datos respectivas de ambos árboles no coinciden, simplemente incrementamos la cantidad de intercambios necesarios
- Una vez que se complete el recorrido, verifique la condición a continuación y devuelva Sí si alguna de las condiciones a continuación es verdadera:
- si nuestro conteo es igual a K, o
- si cuenta es menor que K y (K – cuenta) es par,
- De lo contrario, devuelva No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of above approach
#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class node {
public:
int data;
node* left;
node* right;
};
// Create new node.
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
// Function to convert tree
// into its mirror tree
void convert(node* root)
{
if (!root)
return;
// Recursively call left
// and right node
convert(root->left);
convert(root->right);
// Swap left and right of any node
swap(root->left, root->right);
}
// Function to check identical and
// count no of swap needed to be
int checkIdentical(node* p, node* q)
{
stack<node*> st1, st2;
int count = 0;
while (p || !st1.empty()
&& q || !st2.empty()) {
// If p q are not
// null push in stack
if (p && q) {
st1.push(p);
st2.push(q);
// Send p and q
// to its left child
p = p->left;
q = q->left;
}
// If p and q are null
// pop node from stack
else {
p = st1.top();
q = st2.top();
st1.pop();
st2.pop();
// If data not match
// increment count
if (p->data != q->data)
count++;
// Send p and q to
// its right child
p = p->right;
q = q->right;
}
}
// Return count/2 because
// we swap pairs
return count / 2;
}
/* Driver code*/
int main()
{
node* root1 = newNode(11);
root1->left = newNode(25);
root1->right = newNode(15);
root1->left->left = newNode(7);
root1->left->right = newNode(9);
root1->right->left = newNode(10);
root1->right->right = newNode(21);
node* root2 = newNode(11);
root2->left = newNode(25);
root2->right = newNode(15);
root2->left->left = newNode(10);
root2->left->right = newNode(21);
root2->right->left = newNode(9);
root2->right->right = newNode(7);
int K = 4;
// First convert first
// tree into mirror tree
convert(root1);
int count = checkIdentical(root1, root2);
if (count <= K
&& (K - count) % 2 == 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
class GFG
{
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
public static class node {
int data;
node left;
node right;
}
// Create new node.
public static node newNode(int data)
{
node Node = new node();
Node.data = data;
Node.left = null;
Node.right = null;
return (Node);
}
// Swapping the node
static void swap(node m, node n)
{
// Swapping the values
node temp = m;
m = n;
n = temp;
}
// Function to convert tree
// into its mirror tree
public static void convert(node root)
{
if (root==null)
return;
// Recursively call left
// and right node
convert(root.left);
convert(root.right);
// Swap left and right of any node
swap(root.left, root.right);
}
// Function to check identical and
// count no of swap needed to be
public static int checkIdentical(node p, node q)
{
Stack<node> st1=new Stack<>();
Stack<node> st2=new Stack<>();
int count = 0;
while (p!=null || !st1.empty()
&& q!=null || !st2.empty()) {
// If p q are not
// null push in stack
if (p!=null && q!=null) {
st1.push(p);
st2.push(q);
// Send p and q
// to its left child
p = p.left;
q = q.left;
}
// If p and q are null
// pop node from stack
else {
p = st1.peek();
q = st2.peek();
st1.pop();
st2.pop();
// If data not match
// increment count
if (p.data != q.data)
count++;
// Send p and q to
// its right child
p = p.right;
q = q.right;
}
}
// Return count/2 because
// we swap pairs
return count / 2;
}
// Driver Code
public static void main(String[] args)
{
node root1 = newNode(11);
root1.left = newNode(25);
root1.right = newNode(15);
root1.left.left = newNode(7);
root1.left.right = newNode(9);
root1.right.left = newNode(10);
root1.right.right = newNode(21);
node root2 = newNode(11);
root2.left = newNode(25);
root2.right = newNode(15);
root2.left.left = newNode(10);
root2.left.right = newNode(21);
root2.right.left = newNode(9);
root2.right.right = newNode(7);
int K = 4;
// First convert first
// tree into mirror tree
convert(root1);
int count = checkIdentical(root1, root2);
if (count <= K
&& (K - count) % 2 == 0)
System.out.println("Yes");
else
System.out.println("No");
}
}
// Tthis code is contributed by jana_sayantan.
Python3
# Python code for the above approach
# Node Class
class Node:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
class LinkedList:
def __init__(self):
self.head = None
## Function to convert tree
## into its mirror tree
def convert(head):
if(head == None):
return
## Recursively call left
## and right node
convert(head.left)
convert(head.right)
## Swap left and right of any node
head.left, head.right = head.right, head.left
## Function to check identical and
## count no of swap needed to be
def checkIdentical(head1, head2):
st1 = []
st2 = []
count = 0
while ( (head1!=None) or (len(st1)!=0)) and ( (head2!=None) or (len(st2)!=0)):
## If head1 head2 are not
## none push in stack
if ((head1!=None) and (head2!=None)):
st1.append(head1)
st2.append(head2)
## Send head1 and head2
## to its left child
head1 = head1.left
head2 = head2.left
## If head1 and head2 are null
## pop node from stack
else:
head1 = st1[-1]
head2 = st2[-1]
st1.pop()
st2.pop()
## If data not match
## increment count
if (head1.data != head2.data):
count+=1
## Send head1 and head2 to
## its right child
head1 = head1.right
head2 = head2.right
## Return count/2 because
## we swap pairs
return count / 2
# Driver Code
if __name__=='__main__':
llist1 = LinkedList()
llist1.head = Node(11)
llist1.head.left = Node(25)
llist1.head.right = Node(15)
llist1.head.left.left = Node(7)
llist1.head.left.right = Node(9)
llist1.head.right.left = Node(10)
llist1.head.right.right = Node(21)
llist2 = LinkedList()
llist2.head = Node(11)
llist2.head.left = Node(25)
llist2.head.right = Node(15)
llist2.head.left.left = Node(10)
llist2.head.left.right = Node(21)
llist2.head.right.left = Node(9)
llist2.head.right.right = Node(7)
K = 4
## First convert first
## tree into mirror tree
convert(llist1.head)
count = checkIdentical(llist1.head, llist2.head)
if (count <= K and (K - count) % 2 == 0):
print("Yes")
else:
print("No")
# This code is contributed by subhamgoyal2014.
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
public class GFG
{
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
public class node {
public int data;
public node left;
public node right;
}
// Create new node.
public static node newNode(int data)
{
node Node = new node();
Node.data = data;
Node.left = null;
Node.right = null;
return (Node);
}
// Swapping the node
static void swap(node m, node n)
{
// Swapping the values
node temp = m;
m = n;
n = temp;
}
// Function to convert tree
// into its mirror tree
public static void convert(node root)
{
if (root==null)
return;
// Recursively call left
// and right node
convert(root.left);
convert(root.right);
// Swap left and right of any node
swap(root.left, root.right);
}
// Function to check identical and
// count no of swap needed to be
public static int checkIdentical(node p, node q)
{
Stack<node> st1=new Stack<node>();
Stack<node> st2=new Stack<node>();
int count = 0;
while (p!=null || st1.Count!=0
&& q!=null || st2.Count!=0) {
// If p q are not
// null push in stack
if (p!=null && q!=null) {
st1.Push(p);
st2.Push(q);
// Send p and q
// to its left child
p = p.left;
q = q.left;
}
// If p and q are null
// pop node from stack
else {
p = st1.Peek();
q = st2.Peek();
st1.Pop();
st2.Pop();
// If data not match
// increment count
if (p.data != q.data)
count++;
// Send p and q to
// its right child
p = p.right;
q = q.right;
}
}
// Return count/2 because
// we swap pairs
return count / 2;
}
// Driver Code
public static void Main(String[] args)
{
node root1 = newNode(11);
root1.left = newNode(25);
root1.right = newNode(15);
root1.left.left = newNode(7);
root1.left.right = newNode(9);
root1.right.left = newNode(10);
root1.right.right = newNode(21);
node root2 = newNode(11);
root2.left = newNode(25);
root2.right = newNode(15);
root2.left.left = newNode(10);
root2.left.right = newNode(21);
root2.right.left = newNode(9);
root2.right.right = newNode(7);
int K = 4;
// First convert first
// tree into mirror tree
convert(root1);
int count = checkIdentical(root1, root2);
if (count <= K
&& (K - count) % 2 == 0)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code contributed by shikhasingrajput
Javascript
// Javascript program for the above approach
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class node
{
// Creates new node
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Swapping the node
function swap(m, n) {
// Swapping the values
let temp = m;
m = n;
n = temp;
}
// Function to convert tree
// into its mirror tree
function convert(root) {
if (root == null) {
return;
}
// Recursively call left and right node
convert(root.left);
convert(root.right);
// Swap left and right of any node
swap(root.left, root.right);
}
// Function to check identical and
// count no of swap needed to be
function checkIdentical(p, q) {
let st1 = [];
let st2 = [];
let count = 0;
while (p || st1.length || q || st2.length) {
// If p q are not
// null push in stack
if (p && q) {
st1.push(p);
st2.push(q);
// Send p and q
// to its left child
p = p.left;
q = q.left;
} else {
p = st1[st1.length - 1];
q = st2[st2.length - 1];
st1.pop();
st2.pop();
// If data not match
// increment count
if (p.data != q.data) count++;
// Send p and q to
// its right child
p = p.right;
q = q.right;
}
}
// Return count/2 because
// we swap pairs
return count / 2;
}
// Driver code
let root1 = new node(11);
root1.left = new node(25);
root1.right = new node(15);
root1.left.left = new node(7);
root1.left.right = new node(9);
root1.right.left = new node(10);
root1.right.right = new node(21);
let root2 = new node(11);
root2.left = new node(25);
root2.right = new node(15);
root2.left.left = new node(10);
root2.left.right = new node(21);
root2.right.left = new node(9);
root2.right.right = new node(7);
let k = 4;
// First convert first
// tree into mirror tree
convert(root1);
let count = checkIdentical(root1,root2);
if(count <= k && ((k - count) % 2) == 0){
console.log("Yes");
}else{
console.log("No");
}
// This code is contributed by Ishan Khandelwal
Producción
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)