Compruebe si el árbol N-ario genérico dado es simétrico horizontalmente

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 derecho

Entrada:   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++ 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 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<>();
        }
    }
}

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

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

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