Dada una raíz de árbol N-ario , la tarea es verificar si es simétrica horizontalmente (imagen especular de sí mismo).
Ejemplo:
Entrada: raíz = 7
/ / \ \
4 2 2 4
/ | / | | \ | \
3 2 6 7 7 6 2 3
Salida: verdadero
Explicación: El lado izquierdo del árbol es una imagen especular del lado derechoEntrada: raíz= 2
/ | \
3 4 3
/ | \
5 6 5
Salida: verdadero
Enfoque: El problema dado se puede resolver utilizando el recorrido de preorden . La idea es pasar dos Nodes raíz como parámetros y verificar si el valor de los Nodes actuales es el mismo y usar la recursividad para verificar si el valor de los hijos del Node izquierdo es el mismo que los valores de los hijos del Node derecho.
Se pueden seguir los siguientes pasos para resolver el problema:
- Aplique el recorrido de pre-pedido en el árbol N-ario:
- Compruebe si el valor de ambos Nodes raíz es el mismo o no.
- Además, compruebe si el número de Nodes de ambas raíces es el mismo o no.
- Iterar el Node hijo de la raíz izquierda de izquierda a derecha y simultáneamente iterar los Nodes del Node derecho de derecha a izquierda y usar la recursividad.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
vector<Node *> children;
int val;
// constructor
Node(int v)
{
val = v;
children = {};
}
};
// Preorder traversal to check
// if the generic tree
// is symmetric or not
bool preorder(
Node *root1, Node *root2)
{
// If the values of both the
// root is not the same or if
// the number of children are
// not the same then return false
if (root1->val != root2->val || root1->children.size() != root2->children.size())
return false;
// Number of children
int size = root1->children.size();
// Iterate left to right on
// left root and right to left
// on the right root
for (int i = 0; i < (size+1)/2; i++)
{
// If any one branch is not
// symmetric then return false
if (!preorder(
root1->children[i],
root2->children[size - 1 - i]))
return false;
}
// Tree is symmetric return true
return true;
}
// Function to check if the generic
// tree is symmetric or not
bool isSymmetric(Node *root)
{
// Base case
if (root == NULL)
return true;
// Apply preorder traversal
// on the tree
return preorder(root, root);
}
// Driver code
int main()
{
// Initialize the tree
Node *seven = new Node(7);
Node *five1 = new Node(5);
Node *five2 = new Node(5);
Node *four = new Node(4);
seven->children.push_back(five1);
seven->children.push_back(four);
seven->children.push_back(five2);
// Call the function
// and print the result
if (isSymmetric(seven))
{
cout << "true" << endl;
}
else
{
cout << "false" << endl;
}
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to check if the generic
// tree is symmetric or not
public static boolean isSymmetric(Node root)
{
// Base case
if (root == null)
return true;
// Apply preorder traversal
// on the tree
return preorder(root, root);
}
// Preorder traversal to check
// if the generic tree
// is symmetric or not
public static boolean preorder(
Node root1, Node root2)
{
// If the values of both the
// root is not the same or if
// the number of children are
// not the same then return false
if (root1.val != root2.val
|| root1.children.size()
!= root2.children.size())
return false;
// Number of children
int size = root1.children.size();
// Iterate left to right on
// left root and right to left
// on the right root
for (int i = 0; i < size; i++) {
// If any one branch is not
// symmetric then return false
if (!preorder(
root1.children.get(i),
root2.children.get(size - 1 - i)))
return false;
}
// Tree is symmetric return true
return true;
}
// Driver code
public static void main(String[] args)
{
// Initialize the tree
Node seven = new Node(7);
Node five1 = new Node(5);
Node five2 = new Node(5);
Node four = new Node(4);
seven.children.add(five1);
seven.children.add(four);
seven.children.add(five2);
// Call the function
// and print the result
System.out.println(
isSymmetric(seven));
}
static class Node {
List<Node> children;
int val;
// constructor
public Node(int val)
{
this.val = val;
children = new ArrayList<>();
}
}
}
Python3
# Python code for the above approach
class Node:
def __init__(self, val):
self.val = val
self.children = []
# Preorder traversal to check
# if the generic tree
# is symmetric or not
def preorder(root1, root2):
# If the values of both the
# root is not the same or if
# the number of children are
# not the same then return false
if (root1.val != root2.val or len(root1.children) != len(root2.children)):
return False
# Number of children
size = len(root1.children)
# Iterate left to right on
# left root and right to left
# on the right root
for i in range(0, (size + 1)//2):
# If any one branch is not
# symmetric then return false
if (preorder(root1.children[i],
root2.children[size - 1 - i]) == False):
return False
# Tree is symmetric return true
return True
# Function to check if the generic
# tree is symmetric or not
def isSymmetric(root):
# Base case
if (root == None):
return True
# Apply preorder traversal
# on the tree
return preorder(root, root)
# Driver code
# Initialize the tree
seven = Node(7)
five1 = Node(5)
five2 = Node(5)
four = Node(4)
seven.children.append(five1)
seven.children.append(four)
seven.children.append(five2)
# Call the function
# and print the result
if (isSymmetric(seven)):
print("True")
else:
print("False")
# This code is contributed by rj13to.
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to check if the generic
// tree is symmetric or not
static bool isSymmetric(Node root)
{
// Base case
if (root == null)
return true;
// Apply preorder traversal
// on the tree
return preorder(root, root);
}
// Preorder traversal to check
// if the generic tree
// is symmetric or not
static bool preorder(
Node root1, Node root2)
{
// If the values of both the
// root is not the same or if
// the number of children are
// not the same then return false
if (root1.val != root2.val
|| root1.children.Count
!= root2.children.Count)
return false;
// Number of children
int size = root1.children.Count;
// Iterate left to right on
// left root and right to left
// on the right root
for (int i = 0; i < size; i++) {
// If any one branch is not
// symmetric then return false
if (!preorder(
root1.children[i],
root2.children[size - 1 - i]))
return false;
}
// Tree is symmetric return true
return true;
}
// Driver code
public static void Main(String[] args)
{
// Initialize the tree
Node seven = new Node(7);
Node five1 = new Node(5);
Node five2 = new Node(5);
Node four = new Node(4);
seven.children.Add(five1);
seven.children.Add(four);
seven.children.Add(five2);
// Call the function
// and print the result
Console.WriteLine(
isSymmetric(seven));
}
class Node {
public List<Node> children;
public int val;
// constructor
public Node(int val)
{
this.val = val;
children = new List<Node>();
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript code for the above approach
class Node {
// constructor
constructor(v) {
this.val = v;
this.children = [];
}
};
// Preorder traversal to check
// if the generic tree
// is symmetric or not
function preorder(root1, root2) {
// If the values of both the
// root is not the same or if
// the number of children are
// not the same then return false
if (root1.val != root2.val || root1.children.length != root2.children.length)
return false;
// Number of children
let size = root1.children.length;
// Iterate left to right on
// left root and right to left
// on the right root
for (let i = 0; i < size; i++) {
// If any one branch is not
// symmetric then return false
if (!preorder(
root1.children[i],
root2.children[size - 1 - i]))
return false;
}
// Tree is symmetric return true
return true;
}
// Function to check if the generic
// tree is symmetric or not
function isSymmetric(root) {
// Base case
if (root == null)
return true;
// Apply preorder traversal
// on the tree
return preorder(root, root);
}
// Driver code
// Initialize the tree
let seven = new Node(7);
let five1 = new Node(5);
let five2 = new Node(5);
let four = new Node(4);
seven.children.push(five1);
seven.children.push(four);
seven.children.push(five2);
// Call the function
// and print the result
if (isSymmetric(seven)) {
document.write("true");
}
else {
document.write("false");
}
// This code is contributed by gfgking.
</script>
Producción
true
Complejidad de Tiempo: O(N), donde N es el número de Nodes en el árbol
Espacio Auxiliar: O(H), donde H es la altura del árbol
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