Producto de Nodes en el k-ésimo nivel en un árbol representado como string usando Recursion

Requisito previo: Producto de Nodes en el k-ésimo nivel en un árbol representado como string
Dado un número entero ‘ K ‘ y un árbol binario en formato de string. Cada Node de un árbol tiene un valor en el rango de 0 a 9. Necesitamos encontrar el producto de los elementos en el nivel K-th desde la raíz. La raíz está en el nivel 0.
Nota: El árbol se da en la forma: (valor de Node (subárbol izquierdo) (subárbol derecho))
Ejemplos: 
 

Entrada: Árbol = “(0(5(6()())(4()(9()())))(7(1()())(3()())))” 
k = 2 
Salida: 72 
Explicación: 
Su representación en árbol se muestra a continuación 
 

Los elementos en el nivel k = 2 son 6, 4, 1, 3 
producto de estos elementos = 6 * 4 * 1 * 3 = 72 
Entrada: Árbol = “(8(3(2()())(6(5())())()))(5(10()())(7(13()())())))” 
k = 3 
Salida: 15 
elementos en el nivel k = 3 son 5, 1 y 3 
producto de estos elementos = 5 * 1 * 3 = 15 
 

Enfoque: la idea es tratar la string como un árbol sin crear realmente uno, y simplemente atravesar la string recursivamente en Postorder Fashion y considerar los Nodes que están solo en el nivel k.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation to find product
// of elements at k-th level
 
#include <bits/stdc++.h>
using namespace std;
 
// Recursive Function to find product
// of elements at k-th level
int productAtKthLevel(string tree,
            int k, int& i, int level){
 
    if (tree[i++] == '(') {
 
        // if subtree is null,
        // just like if root == NULL
        if (tree[i] == ')')
            return 1;
 
        int product = 1;
 
        // Consider only level k node
        // to be part of the product
        if (level == k)
            product = tree[i] - '0';
 
        // Recur for Left Subtree
        int leftproduct = productAtKthLevel(
                    tree, k, ++i, level + 1);
 
        // Recur for Right Subtree
        int rightproduct = productAtKthLevel(
                tree, k, ++i, level + 1);
 
        // Taking care of ')' after
        // left and right subtree
        ++i;
        return product * leftproduct *
                       rightproduct;
    }
}
 
// Driver Code
int main()
{
    string tree = "(0(5(6()())(4()"
    "(9()())))(7(1()())(3()())))";
    int k = 2;
    int i = 0;
 
    cout << productAtKthLevel(tree, k, i, 0);
 
    return 0;
}

Java

// Java implementation to find
// product of elements at k-th level
 
class GFG {
    static int i;
 
    // Recursive Function to find product
    // of elements at k-th level
    static int productAtKthLevel(
        String tree, int k, int level){
 
        if (tree.charAt(i++) == '(') {
 
            // if subtree is null,
            // just like if root == null
            if (tree.charAt(i) == ')')
                return 1;
 
            int product = 1;
 
            // Consider only level k node
            // to be part of the product
            if (level == k)
                product = tree.charAt(i) - '0';
 
            // Recur for Left Subtree
            ++i;
            int leftproduct = productAtKthLevel(
                            tree, k, level + 1);
 
            // Recur for Right Subtree
            ++i;
            int rightproduct = productAtKthLevel(
                            tree, k, level + 1);
 
            // Taking care of ')' after
            // left and right subtree
            ++i;
            return product * leftproduct
              * rightproduct;
        }
        return Integer.MIN_VALUE;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String tree = "(0(5(6()())(4()"
        + "(9()())))(7(1()())(3()())))";
        int k = 2;
        i = 0;
        System.out.print(
            productAtKthLevel(tree, k, 0)
        );
    }
}

Python

# Python implementation to find product of
# digits of elements at k-th level
 
# Recursive Function to find product
# of elements at k-th level
def productAtKthLevel(tree, k, i, level):
     
    if(tree[i[0]]=='('):
        i[0]+= 1
        # if subtree is null,
        # just like if root == NULL
        if(tree[i[0]] == ')'):
            return 1           
         
        product = 1
        # Consider only level k node
        # to be part of the product
        if(level == k):
            product = int(tree[i[0]])
             
        # Recur for Left Subtree
        i[0]+= 1
        leftproduct = productAtKthLevel(tree,
                            k, i, level + 1)
             
        # Recur for Right Subtree
        i[0]+= 1
        rightproduct = productAtKthLevel(tree,
                            k, i, level + 1)
             
        # Taking care of ')' after left and right subtree
        i[0]+= 1
        return product * leftproduct * rightproduct        
     
# Driver Code
if __name__ == "__main__":
    tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))"
    k = 2
    i =[0]
    print(productAtKthLevel(tree, k, i, 0))

C#

// C# implementation to find product
// of elements at k-th level
 
using System;
 
class GFG {
    static int i;
 
    // Recursive Function to find product
    // of elements at k-th level
    static int productAtKthLevel(
        String tree, int k, int level){
 
        if (tree[i++] == '(') {
 
            // if subtree is null,
            // just like if root == null
            if (tree[i] == ')')
                return 1;
 
            int product = 1;
 
            // Consider only level k node
            // to be part of the product
            if (level == k)
                product = tree[i] - '0';
 
            // Recur for Left Subtree
            ++i;
            int leftproduct = productAtKthLevel(
                            tree, k, level + 1);
 
            // Recur for Right Subtree
            ++i;
            int rightproduct =
            productAtKthLevel(tree, k, level + 1);
 
            // Taking care of ')' after
            // left and right subtree
            ++i;
            return product *
              leftproduct * rightproduct;
        }
        return int.MinValue;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String tree = "(0(5(6()())(4()"
        +"(9()())))(7(1()())(3()())))";
        int k = 2;
        i = 0;
        Console.Write(productAtKthLevel(tree, k, 0));
    }
}

Javascript

<script>
 
// JavaScript implementation to find product
// of elements at k-th level
var i;
// Recursive Function to find product
// of elements at k-th level
function productAtKthLevel( tree, k, level){
    if (tree[i++] == '(') {
        // if subtree is null,
        // just like if root == null
        if (tree[i] == ')')
            return 1;
        var product = 1;
        // Consider only level k node
        // to be part of the product
        if (level == k)
            product = tree[i] - '0';
        // Recur for Left Subtree
        ++i;
        var leftproduct = productAtKthLevel(
                        tree, k, level + 1);
        // Recur for Right Subtree
        ++i;
        var rightproduct =
        productAtKthLevel(tree, k, level + 1);
        // Taking care of ')' after
        // left and right subtree
        ++i;
        return product *
          leftproduct * rightproduct;
    }
    return int.MinValue;
}
// Driver Code
var tree = "(0(5(6()())(4()(9()())))(7(1()())(3()())))";
var k = 2;
i = 0;
document.write(productAtKthLevel(tree, k, 0));
 
 
</script>
Producción: 

72

 

Complejidad de tiempo: O(N)
 

Publicación traducida automáticamente

Artículo escrito por SHUBHAMSINGH10 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 *