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