Convierta el árbol binario dado en un árbol simétrico agregando un número mínimo de Nodes

Posted on by Rudeus Greyrat

Dado un árbol binario , la tarea es convertir el árbol binario dado en el árbol simétrico agregando el número mínimo de Nodes en el árbol dado.

Ejemplos:

Aporte: 

Producción:

Aporte: 

Producción:

Enfoque: Para resolver este problema, siga los pasos a continuación:

  1. Cree una función buildSymmetricTree que acepte dos parámetros root1 y root2 .
  2. Aquí, root1 y root2 son los Nodes que están en lugares simétricos entre sí.
  3. Entonces, inicialmente, tanto root1 como root2 contendrán el valor de la raíz y en cada llamada recursiva:
    • Si root1 existe pero root2 no, cree un nuevo Node con el mismo valor que root1 y colóquelo en la posición de root2 .
    • Siga el paso anterior también para root1 si root2 existe pero root1 no.
    • Si el valor de root1 y root2 no es el mismo, cambie el valor de ambos Nodes a la suma de ellos.
    • Ahora, realice las siguientes dos llamadas recursivas para las posiciones simétricas en (raíz1->izquierda, raíz2->derecha) y (raíz1->derecha, raíz2->izquierda).
  4. El árbol se volverá simétrico después de que se realicen todas las llamadas recursivas.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Node
class Node {
public:
    int val;
    Node *left, *right;
    Node(int val)
    {
        this->val = val;
        left = right = NULL;
    }
};
 
// Function to convert the given tree
// into a symmetric
Node* buidSymmetricTree(Node* root1,
                         Node* root2)
{
    // Base Case
    if (root1 == NULL and root2 == NULL) {
        return NULL;
    }
 
    // If root1 == NULL & root2 != NULL
    if (root1 == NULL) {
 
        // Create new node for root2
        // and attaching it to tree
        Node* node = new Node(root2->val);
        root1 = node;
    }
 
    // If root2 == NULL and root1 != NULL
    if (root2 == NULL) {
 
        // Create new node for root1
        // and attaching it to tree
        Node* node = new Node(root1->val);
        root2 = node;
    }
 
    // If both nodes are different
    // then change both nodes values
    // to the sum of them
    if (root1->val != root2->val) {
        int temp = root1->val + root2->val;
        root1->val = temp;
        root2->val = temp;
    }
 
    // Recurring to the left
    root1->left
        = buidSymmetricTree(
            root1->left, root2->right);
 
    // Recurring to the right
    root1->right
        = buidSymmetricTree(
            root1->right, root2->left);
 
    // Return root pointer
    return root1;
}
 
// Function to perform the Inorder
// Traversal of the tree
void inorder(Node* root)
{
    // Base Case
    if (root == NULL)
        return;
 
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}
 
// Driver Code
int main()
{
    Node* root = new Node(3);
    root->left = new Node(2);
    root->right = new Node(4);
    root->left->left = new Node(5);
 
    // Function to make the given
    // tree symmetric
    buidSymmetericTree(root, root);
 
    // Print the inorder traversal
    inorder(root);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Node
static class Node {
    int val;
    Node left, right;
    Node(int val)
    {
        this.val = val;
        left = right = null;
    }
};
 
// Function to convert the given tree
// into a symmetric
static Node buidSymmetricTree(Node root1,
                         Node root2)
{
    // Base Case
    if (root1 == null && root2 == null) {
        return null;
    }
 
    // If root1 == null & root2 != null
    if (root1 == null) {
 
        // Create new node for root2
        // and attaching it to tree
        Node node = new Node(root2.val);
        root1 = node;
    }
 
    // If root2 == null and root1 != null
    if (root2 == null) {
 
        // Create new node for root1
        // and attaching it to tree
        Node node = new Node(root1.val);
        root2 = node;
    }
 
    // If both nodes are different
    // then change both nodes values
    // to the sum of them
    if (root1.val != root2.val) {
        int temp = root1.val + root2.val;
        root1.val = temp;
        root2.val = temp;
    }
 
    // Recurring to the left
    root1.left
        = buidSymmetricTree(
            root1.left, root2.right);
 
    // Recurring to the right
    root1.right
        = buidSymmetricTree(
            root1.right, root2.left);
 
    // Return root pointer
    return root1;
}
 
// Function to perform the Inorder
// Traversal of the tree
static void inorder(Node root)
{
    // Base Case
    if (root == null)
        return;
 
    inorder(root.left);
    System.out.print(root.val+ " ");
    inorder(root.right);
}
 
// Driver Code
public static void main(String[] args)
{
    Node root = new Node(3);
    root.left = new Node(2);
    root.right = new Node(4);
    root.left.left = new Node(5);
 
    // Function to make the given
    // tree symmetric
    buidSymmetericTree(root, root);
 
    // Print the inorder traversal
    inorder(root);
}
}
 
// This code is contributed by umadevi9616

Python3

# Python Program to implement
# the above approach
 
# Node
class Node:
 
    def __init__(self, val):
        self.val = val
        self.left = self.right = None
     
 
 
# Function to convert the given tree
# into a symmetric
def buidSymmetricTree(root1, root2):
    # Base Case
    if (root1 == None and root2 == None):
        return None
     
 
    # If root1 == null & root2 != null
    if (root1 == None):
 
        # Create new node for root2
        # and attaching it to tree
        node = Node(root2.val)
        root1 = node
     
 
    # If root2 == null and root1 != null
    if (root2 == None):
 
        # Create new node for root1
        # and attaching it to tree
        node = Node(root1.val)
        root2 = node
     
 
    # If both nodes are different
    # then change both nodes values
    # to the sum of them
    if (root1.val != root2.val):
        temp = root1.val + root2.val
        root1.val = temp
        root2.val = temp
     
 
    # Recurring to the left
    root1.left = buidSymmetricTree( root1.left, root2.right)
 
    # Recurring to the right
    root1.right = buidSymmetricTree(root1.right, root2.left)
 
    # Return root pointer
    return root1
 
 
# Function to perform the Inorder
# Traversal of the tree
def inorder(root):
    # Base Case
    if (root == None):
      return
 
    inorder(root.left)
    print(root.val, end=" ")
    inorder(root.right)
 
 
# Driver Code
 
root = Node(3)
root.left = Node(2)
root.right = Node(4)
root.left.left = Node(5)
 
# Function to make the given
# tree symmetric
buidSymmetericTree(root, root)
 
# Print the inorder traversal
inorder(root)
 
# This code is contributed by gfgking.

C#

// C# program for the above approach
using System;
public class GFG {
 
    // Node
public    class Node {
    public    int val;
    public    Node left, right;
 
    public    Node(int val) {
            this.val = val;
            left = right = null;
        }
    };
 
    // Function to convert the given tree
    // into a symmetric
    static Node buidSymmetricTree(Node root1, Node root2)
    {
       
        // Base Case
        if (root1 == null && root2 == null) {
            return null;
        }
 
        // If root1 == null & root2 != null
        if (root1 == null) {
 
            // Create new node for root2
            // and attaching it to tree
            Node node = new Node(root2.val);
            root1 = node;
        }
 
        // If root2 == null and root1 != null
        if (root2 == null) {
 
            // Create new node for root1
            // and attaching it to tree
            Node node = new Node(root1.val);
            root2 = node;
        }
 
        // If both nodes are different
        // then change both nodes values
        // to the sum of them
        if (root1.val != root2.val) {
            int temp = root1.val + root2.val;
            root1.val = temp;
            root2.val = temp;
        }
 
        // Recurring to the left
        root1.left = buidSymmetricTree(root1.left, root2.right);
 
        // Recurring to the right
        root1.right = buidSymmetricTree(root1.right, root2.left);
 
        // Return root pointer
        return root1;
    }
 
    // Function to perform the Inorder
    // Traversal of the tree
    static void inorder(Node root)
    {
       
        // Base Case
        if (root == null)
            return;
 
        inorder(root.left);
        Console.Write(root.val + " ");
        inorder(root.right);
    }
 
    // Driver Code
    public static void Main(String[] args) {
        Node root = new Node(3);
        root.left = new Node(2);
        root.right = new Node(4);
        root.left.left = new Node(5);
 
        // Function to make the given
        // tree symmetric
        buidSymmetericTree(root, root);
 
        // Print the inorder traversal
        inorder(root);
    }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
 
        // Node
        class Node {
 
            constructor(val) {
                this.val = val;
                this.left = this.right = null;
            }
        };
 
        // Function to convert the given tree
        // into a symmetric
        function buidSymmetricTree(root1,
            root2) {
            // Base Case
            if (root1 == null && root2 == null) {
                return null;
            }
 
            // If root1 == null & root2 != null
            if (root1 == null) {
 
                // Create new node for root2
                // and attaching it to tree
                let node = new Node(root2.val);
                root1 = node;
            }
 
            // If root2 == null and root1 != null
            if (root2 == null) {
 
                // Create new node for root1
                // and attaching it to tree
                let node = new Node(root1.val);
                root2 = node;
            }
 
            // If both nodes are different
            // then change both nodes values
            // to the sum of them
            if (root1.val != root2.val) {
                let temp = root1.val + root2.val;
                root1.val = temp;
                root2.val = temp;
            }
 
            // Recurring to the left
            root1.left
                = buidSymmetricTree(
                    root1.left, root2.right);
 
            // Recurring to the right
            root1.right
                = buidSymmetricTree(
                    root1.right, root2.left);
 
            // Return root pointer
            return root1;
        }
 
        // Function to perform the Inorder
        // Traversal of the tree
        function inorder(root) {
            // Base Case
            if (root == null)
                return;
 
            inorder(root.left);
            document.write(root.val + " ");
            inorder(root.right);
        }
 
        // Driver Code
 
        let root = new Node(3);
        root.left = new Node(2);
        root.right = new Node(4);
        root.left.left = new Node(5);
 
        // Function to make the given
        // tree symmetric
        buidSymmetericTree(root, root);
 
        // Print the inorder traversal
        inorder(root);
 
// This code is contributed by Potta Lokesh
    </script>
Producción: 

5 6 3 6 5

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por vibhor11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *