Dado un árbol binario , la tarea es contar el número de caminos exponenciales en el árbol binario dado.
La ruta exponencial es una ruta donde la ruta de la raíz a la hoja contiene todos los Nodes que son iguales a x y , donde x es una constante positiva mínima posible e y es un número entero positivo variable.
Ejemplo:
Input:
27
/ \
9 81
/ \ / \
3 10 70 243
/ \
81 909
Output: 2
Explanation:
There are 2 exponential path for
the above Binary Tree, for x = 3,
Path 1: 27 -> 9 -> 3
Path 2: 27 -> 81 -> 243 -> 81
Input:
8
/ \
4 81
/ \ / \
3 2 70 243
/ \
81 909
Output: 1
Enfoque: La idea es usar Preorder Tree Traversal . Durante el recorrido previo al pedido del árbol binario dado, haga lo siguiente:
- Primero encuentre el valor de x para el cual x y = raíz & x es el mínimo posible & y>0.
- Si el valor actual del Node no es igual a x y para algún y>0, o el puntero se convierte en NULL , devuelve el recuento.
- Si el Node actual es un Node hoja, incremente el conteo en 1.
- Llame recursivamente al subárbol izquierdo y derecho con el recuento actualizado.
- Después de todas las llamadas recursivas, el valor de la cuenta es el número de caminos exponenciales para un árbol binario dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the count
// exponential paths in Binary Tree
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left
= temp->right
= NULL;
return (temp);
}
// function to find x
int find_x(int n)
{
if (n == 1)
return 1;
double num, den, p;
// Take log10 of n
num = log10(n);
int x, no;
for (int i = 2; i <= n; i++) {
den = log10(i);
// Log(n) with base i
p = num / den;
// Raising i to the power p
no = (int)(pow(i, int(p)));
if (abs(no - n) < 1e-6) {
x = i;
break;
}
}
return x;
}
// function To check
// whether the given node
// equals to x^y for some y>0
bool is_key(int n, int x)
{
double p;
// Take logx(n) with base x
p = log10(n) / log10(x);
int no = (int)(pow(x, int(p)));
if (n == no)
return true;
return false;
}
// Utility function to count
// the exponent path
// in a given Binary tree
int evenPaths(struct Node* node,
int count, int x)
{
// Base Condition, when node pointer
// becomes null or node value is not
// a number of pow(x, y )
if (node == NULL
|| !is_key(node->key, x)) {
return count;
}
// Increment count when
// encounter leaf node
if (!node->left
&& !node->right) {
count++;
}
// Left recursive call
// save the value of count
count = evenPaths(
node->left, count, x);
// Right recursive call and
// return value of count
return evenPaths(
node->right, count, x);
}
// function to count exponential paths
int countExpPaths(
struct Node* node, int x)
{
return evenPaths(node, 0, x);
}
// Driver Code
int main()
{
// create Tree
Node* root = newNode(27);
root->left = newNode(9);
root->right = newNode(81);
root->left->left = newNode(3);
root->left->right = newNode(10);
root->right->left = newNode(70);
root->right->right = newNode(243);
root->right->right->left = newNode(81);
root->right->right->right = newNode(909);
// retrieve the value of x
int x = find_x(root->key);
// Function call
cout << countExpPaths(root, x);
return 0;
}
Java
// Java program to find the count
// exponential paths in Binary Tree
import java.util.*;
import java.lang.*;
class GFG{
// Structure of a Tree node
static class Node
{
int key;
Node left, right;
}
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to find x
static int find_x(int n)
{
if (n == 1)
return 1;
double num, den, p;
// Take log10 of n
num = Math.log10(n);
int x = 0, no = 0;
for(int i = 2; i <= n; i++)
{
den = Math.log10(i);
// Log(n) with base i
p = num / den;
// Raising i to the power p
no = (int)(Math.pow(i, (int)p));
if (Math.abs(no - n) < 1e-6)
{
x = i;
break;
}
}
return x;
}
// Function to check whether the
// given node equals to x^y for some y>0
static boolean is_key(int n, int x)
{
double p;
// Take logx(n) with base x
p = Math.log10(n) / Math.log10(x);
int no = (int)(Math.pow(x, (int)p));
if (n == no)
return true;
return false;
}
// Utility function to count
// the exponent path in a
// given Binary tree
static int evenPaths(Node node, int count,
int x)
{
// Base Condition, when node pointer
// becomes null or node value is not
// a number of pow(x, y )
if (node == null || !is_key(node.key, x))
{
return count;
}
// Increment count when
// encounter leaf node
if (node.left == null &&
node.right == null)
{
count++;
}
// Left recursive call
// save the value of count
count = evenPaths(node.left,
count, x);
// Right recursive call and
// return value of count
return evenPaths(node.right,
count, x);
}
// Function to count exponential paths
static int countExpPaths(Node node, int x)
{
return evenPaths(node, 0, x);
}
// Driver code
public static void main(String[] args)
{
// Create Tree
Node root = newNode(27);
root.left = newNode(9);
root.right = newNode(81);
root.left.left = newNode(3);
root.left.right = newNode(10);
root.right.left = newNode(70);
root.right.right = newNode(243);
root.right.right.left = newNode(81);
root.right.right.right = newNode(909);
// Retrieve the value of x
int x = find_x(root.key);
// Function call
System.out.println(countExpPaths(root, x));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the count # exponential paths in Binary Tree import math # Structure of a Tree node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to create a new node def newNode(key): temp = Node(key) return temp # Function to find x def find_x(n): if n == 1: return 1 # Take log10 of n num = math.log10(n) x, no = 0, 0 for i in range(2, n + 1): den = math.log10(i) # Log(n) with base i p = num / den # Raising i to the power p no = int(pow(i, int(p))) if abs(no - n) < 1e-6: x = i break return x # Function to check whether the # given node equals to x^y for some y>0 def is_key(n, x): # Take logx(n) with base x p = math.log10(n) / math.log10(x) no = int(pow(x, int(p))) if n == no: return True return False # Utility function to count # the exponent path in a # given Binary tree def evenPaths(node, count, x): # Base Condition, when node pointer # becomes null or node value is not # a number of pow(x, y ) if node == None or not is_key(node.key, x): return count # Increment count when # encounter leaf node if node.left == None and node.right == None: count+=1 # Left recursive call # save the value of count count = evenPaths(node.left, count, x) # Right recursive call and # return value of count return evenPaths(node.right, count, x) # Function to count exponential paths def countExpPaths(node, x): return evenPaths(node, 0, x) # Create Tree root = newNode(27) root.left = newNode(9) root.right = newNode(81) root.left.left = newNode(3) root.left.right = newNode(10) root.right.left = newNode(70) root.right.right = newNode(243) root.right.right.left = newNode(81) root.right.right.right = newNode(909) # Retrieve the value of x x = find_x(root.key) # Function call print(countExpPaths(root, x)) # This code is contributed by divyeshrabadiya07.
C#
// C# program to find the count
// exponential paths in Binary Tree
using System;
class GFG{
// Structure of a Tree node
public class Node
{
public int key;
public Node left, right;
}
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to find x
static int find_x(int n)
{
if (n == 1)
return 1;
double num, den, p;
// Take log10 of n
num = Math.Log10(n);
int x = 0, no = 0;
for(int i = 2; i <= n; i++)
{
den = Math.Log10(i);
// Log(n) with base i
p = num / den;
// Raising i to the power p
no = (int)(Math.Pow(i, (int)p));
if (Math.Abs(no - n) < 0.000001)
{
x = i;
break;
}
}
return x;
}
// Function to check whether the
// given node equals to x^y for some y>0
static bool is_key(int n, int x)
{
double p;
// Take logx(n) with base x
p = Math.Log10(n) / Math.Log10(x);
int no = (int)(Math.Pow(x, (int)p));
if (n == no)
return true;
return false;
}
// Utility function to count
// the exponent path in a
// given Binary tree
static int evenPaths(Node node, int count,
int x)
{
// Base Condition, when node pointer
// becomes null or node value is not
// a number of pow(x, y )
if (node == null || !is_key(node.key, x))
{
return count;
}
// Increment count when
// encounter leaf node
if (node.left == null &&
node.right == null)
{
count++;
}
// Left recursive call
// save the value of count
count = evenPaths(node.left,
count, x);
// Right recursive call and
// return value of count
return evenPaths(node.right,
count, x);
}
// Function to count exponential paths
static int countExpPaths(Node node, int x)
{
return evenPaths(node, 0, x);
}
// Driver code
public static void Main(string[] args)
{
// Create Tree
Node root = newNode(27);
root.left = newNode(9);
root.right = newNode(81);
root.left.left = newNode(3);
root.left.right = newNode(10);
root.right.left = newNode(70);
root.right.right = newNode(243);
root.right.right.left = newNode(81);
root.right.right.right = newNode(909);
// Retrieve the value of x
int x = find_x(root.key);
// Function call
Console.Write(countExpPaths(root, x));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find the count
// exponential paths in Binary Tree
// Structure of a Tree node
class Node
{
constructor(key)
{
this.left = null;
this.right = null;
this.key = key;
}
}
// Function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
// Function to find x
function find_x(n)
{
if (n == 1)
return 1;
let num, den, p;
// Take log10 of n
num = Math.log10(n);
let x = 0, no = 0;
for(let i = 2; i <= n; i++)
{
den = Math.log10(i);
// Log(n) with base i
p = num / den;
// Raising i to the power p
no = parseInt(Math.pow(
i, parseInt(p, 10)), 10);
if (Math.abs(no - n) < 1e-6)
{
x = i;
break;
}
}
return x;
}
// Function to check whether the
// given node equals to x^y for some y>0
function is_key(n, x)
{
let p;
// Take logx(n) with base x
p = Math.log10(n) / Math.log10(x);
let no = parseInt(Math.pow(
x, parseInt(p, 10)), 10);
if (n == no)
return true;
return false;
}
// Utility function to count
// the exponent path in a
// given Binary tree
function evenPaths(node, count, x)
{
// Base Condition, when node pointer
// becomes null or node value is not
// a number of pow(x, y )
if (node == null || !is_key(node.key, x))
{
return count;
}
// Increment count when
// encounter leaf node
if (node.left == null &&
node.right == null)
{
count++;
}
// Left recursive call
// save the value of count
count = evenPaths(node.left,
count, x);
// Right recursive call and
// return value of count
return evenPaths(node.right,
count, x);
}
// Function to count exponential paths
function countExpPaths(node, x)
{
return evenPaths(node, 0, x);
}
// Driver code
// Create Tree
let root = newNode(27);
root.left = newNode(9);
root.right = newNode(81);
root.left.left = newNode(3);
root.left.right = newNode(10);
root.right.left = newNode(70);
root.right.right = newNode(243);
root.right.right.left = newNode(81);
root.right.right.right = newNode(909);
// Retrieve the value of x
let x = find_x(root.key);
// Function call
document.write(countExpPaths(root, x));
// This code is contributed by mukesh07
</script>
Producción:
2