Dado un árbol binario que consta de N Nodes, la tarea es encontrar el número de rutas desde la raíz hasta cualquier Node X , de modo que todos los valores de Node en esa ruta sean como máximo X.
Ejemplos:
Entrada: A continuación se muestra el árbol dado:
Salida: 4
Explicación:
Las rutas desde la raíz hasta cualquier Node X que tengan valor en la mayoría de los valores del Node X son:
- Node 3 (Node raíz): Siempre sigue la propiedad dada.
- Node 4: El camino que parte de la raíz al Node con valor 4 tiene orden (3 → 4), siendo el valor máximo de un Node 4.
- Node 5: El camino que parte de la raíz al Node con valor 5 tiene orden (3 → 4 → 5), siendo el valor máximo de un Node 5.
- Node 3: El camino que parte de la raíz al Node con valor 3 tiene orden (3 → 1 → 3), siendo el valor máximo de un Node 3.
Por lo tanto, el recuento de rutas requeridas es 4.
Entrada: A continuación se muestra el árbol dado:
Salida: 3
Enfoque – usando DFS: La idea es atravesar el árbol usando un recorrido de búsqueda en profundidad primero mientras se verifica si el valor máximo desde la raíz hasta cualquier Node X es igual a X o no.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar como 0 para almacenar el recuento de rutas desde la raíz hasta cualquier Node X que tenga todos los valores de Node en esa ruta como máximo X .
- Atraviese el árbol recursivamente utilizando la búsqueda en profundidad y realice los siguientes pasos:
- Cada llamada recursiva para DFS Traversal, además del Node padre , pasa el valor máximo del Node obtenido hasta el momento en esa ruta.
- Verifique si el valor del Node actual es mayor o igual al valor máximo obtenido hasta el momento, luego incremente el valor de conteo en 1 y actualice el valor máximo al valor del Node actual.
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
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 structure of the binary tree
struct Node {
int val;
Node *left, *right;
};
// Function for creating new node
struct Node* newNode(int data)
{
// Allocate memory for new node
struct Node* temp = new Node();
// Assigning data value
temp->val = data;
temp->left = NULL;
temp->right = NULL;
// Return the Node
return temp;
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
int countNodes(Node* root, int max)
{
// If the root node is NULL
if (!root)
return 0;
// Check if the current value is
// greater than the maximum value
// in path from root to current node
if (root->val >= max)
return 1 + countNodes(root->left,
root->val)
+ countNodes(root->right, root->val);
// Otherwise
return countNodes(root->left,
max)
+ countNodes(root->right,
max);
}
// Driver Code
int main()
{
// Given Binary Tree
Node* root = NULL;
root = newNode(3);
root->left = newNode(1);
root->right = newNode(4);
root->left->left = newNode(3);
root->right->left = newNode(1);
root->right->right = newNode(5);
cout << countNodes(root, INT_MIN);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
// Class containing left and
// right child of current
// node and key value
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class GFG {
// Root of the Binary Tree
Node root;
public GFG()
{
root = null;
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
static int countNodes(Node root, int max)
{
// If the root node is NULL
if (root == null)
return 0;
// Check if the current value is
// greater than the maximum value
// in path from root to current node
if (root.data >= max)
return 1 + countNodes(root.left,
root.data)
+ countNodes(root.right, root.data);
// Otherwise
return countNodes(root.left,
max)
+ countNodes(root.right,
max);
}
// Driver code
public static void main (String[] args)
{
GFG tree = new GFG();
tree.root = new Node(3);
tree.root.left = new Node(1);
tree.root.right = new Node(4);
tree.root.left.left = new Node(3);
tree.root.right.left = new Node(1);
tree.root.right.right = new Node(5);
System.out.println(countNodes(tree.root, Integer.MIN_VALUE));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Node structure of the binary tree class Node: def __init__(self, x): self.val = x self.left = None self.right = None # Function to perform the DFS Traversal # to find the number of paths having # root to node X has value at most X def countNodes(root, max): # If the root node is NULL if (not root): return 0 # Check if the current value is # greater than the maximum value #in path from root to current node if (root.val >= max): return 1 + countNodes(root.left,root.val) + countNodes(root.right, root.val) # Otherwise return countNodes(root.left, max) + countNodes(root.right, max) # Driver Code if __name__ == '__main__': # Given Binary Tree root = Node(3) root.left = Node(1) root.right = Node(4) root.left.left = Node(3) root.right.left = Node(1) root.right.right = Node(5) print(countNodes(root, -10**19)) # This code is contributed by mohit kumar 29.
C#
// C# program to count frequencies of array items
using System;
// Class containing left and
// right child of current
// node and key value
class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class GFG
{
// Root of the Binary Tree
Node root;
public GFG()
{
root = null;
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
static int countNodes(Node root, int max)
{
// If the root node is NULL
if (root == null)
return 0;
// Check if the current value is
// greater than the maximum value
// in path from root to current node
if (root.data >= max)
return 1 + countNodes(root.left,
root.data)
+ countNodes(root.right, root.data);
// Otherwise
return countNodes(root.left,
max)
+ countNodes(root.right,
max);
}
// Driver code
public static void Main(String []args)
{
GFG tree = new GFG();
tree.root = new Node(3);
tree.root.left = new Node(1);
tree.root.right = new Node(4);
tree.root.left.left = new Node(3);
tree.root.right.left = new Node(1);
tree.root.right.right = new Node(5);
Console.WriteLine(countNodes(tree.root, Int32.MinValue));
}
}
// This code is contributed by jana_sayantan.
Javascript
<script>
// Javascript program for the above approach
// Class containing left and
// right child of current
// node and key value
class Node
{
constructor(item) {
this.left = null;
this.right = null;
this.data = item;
}
}
// Root of the Binary Tree
let root;
class GFG
{
constructor() {
root = null;
}
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
function countNodes(root, max)
{
// If the root node is NULL
if (root == null)
return 0;
// Check if the current value is
// greater than the maximum value
// in path from root to current node
if (root.data >= max)
return 1 + countNodes(root.left, root.data)
+ countNodes(root.right, root.data);
// Otherwise
return countNodes(root.left, max)
+ countNodes(root.right, max);
}
let tree = new GFG();
tree.root = new Node(3);
tree.root.left = new Node(1);
tree.root.right = new Node(4);
tree.root.left.left = new Node(3);
tree.root.right.left = new Node(1);
tree.root.right.right = new Node(5);
document.write(countNodes(tree.root, Number.MIN_VALUE));
// This code is contributed by sureh07.
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque usando BFS: la idea es atravesar el árbol usando la búsqueda primero en amplitud mientras se verifica si el valor máximo desde la raíz hasta X es igual a X . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar como 0 para almacenar el recuento de rutas desde la raíz hasta cualquier Node X que tenga todos los valores de Node en esa ruta como máximo X y una cola Q de pares para realizar el BFS Traversal.
- Empuje el Node raíz con INT_MIN como valor máximo en la cola.
- Ahora, hasta que Q no esté vacío, realice lo siguiente:
- Extraiga el Node frontal de la cola .
- Si el valor del Node frontal es al menos el valor máximo actual obtenido hasta el momento, incremente el valor de count en 1 .
- Actualice el valor máximo que se produjo hasta el momento con el valor del Node actual.
- Si los Nodes izquierdo y derecho existen para el Node emergente actual, introdúzcalo en la cola Q con el valor máximo actualizado en el paso anterior.
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
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 of the binary tree
struct Node {
int val;
Node *left, *right;
};
// Function for creating new node
struct Node* newNode(int data)
{
// Allocate memory for new node
struct Node* temp = new Node();
temp->val = data;
temp->left = NULL;
temp->right = NULL;
// Return the created node
return temp;
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
int countNodes(Node* root)
{
// Initialize queue
queue<pair<Node*, int> > q;
int m = INT_MIN;
// Push root in queue with the
// maximum value m
q.push({ root, m });
// Stores the count of good nodes
int count = 0;
// Traverse all nodes
while (!q.empty()) {
// Store the front node of
// the queue
auto temp = q.front();
q.pop();
Node* node = temp.first;
int num = temp.second;
// Check is current node is
// greater than the maximum
// value in path from root to
// the current node
if (node->val >= num)
count++;
// Update the maximum value m
m = max(node->val, num);
// If left child is not null,
// push it to queue with the
// maximum value m
if (node->left)
q.push({ node->left, m });
// If right child is not null,
// push it to queue with the
// maximum value m
if (node->right)
q.push({ node->right, m });
}
// Returns the answer
return count;
}
// Driver Code
int main()
{
// Construct a Binary Tree
Node* root = NULL;
root = newNode(3);
root->left = newNode(1);
root->right = newNode(4);
root->left->left = newNode(3);
root->right->left = newNode(1);
root->right->right = newNode(5);
cout << countNodes(root);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
// Node of the binary tree
class Node {
int val;
Node left, right;
public Node(int data)
{
val = data;
left = right = null;
}
}
// User defined Pair class
class Pair {
Node x;
int y;
// Constructor
public Pair(Node x, int y)
{
this.x = x;
this.y = y;
}
}
public class Main
{
// Function for creating new node
static Node newNode(int data)
{
// Allocate memory for new node
Node temp = new Node(data);
// Return the created node
return temp;
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
static int countNodes(Node root)
{
// Initialize queue
Vector<Pair> q = new Vector<Pair>();
int m = Integer.MIN_VALUE;
// Push root in queue with the
// maximum value m
q.add(new Pair(root, m));
// Stores the count of good nodes
int count = 0;
// Traverse all nodes
while (q.size() > 0) {
// Store the front node of
// the queue
Pair temp = q.get(0);
q.remove(0);
Node node = temp.x;
int num = temp.y;
// Check is current node is
// greater than the maximum
// value in path from root to
// the current node
if (node.val >= num)
count++;
// Update the maximum value m
m = Math.max(node.val, num);
// If left child is not null,
// push it to queue with the
// maximum value m
if (node.left != null)
q.add(new Pair(node.left, m));
// If right child is not null,
// push it to queue with the
// maximum value m
if (node.right != null)
q.add(new Pair(node.right, m));
}
// Returns the answer
return count;
}
public static void main(String[] args) {
// Construct a Binary Tree
Node root = null;
root = newNode(3);
root.left = newNode(1);
root.right = newNode(4);
root.left.left = newNode(3);
root.right.left = newNode(1);
root.right.right = newNode(5);
System.out.println(countNodes(root));
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program for the above approach import sys # Node of the binary tree class Node: def __init__(self, data): self.val = data self.left = None self.right = None # Function for creating new node def newNode(data): # Allocate memory for new node temp = Node(data) # Return the created node return temp # Function to perform the DFS Traversal # to find the number of paths having # root to node X has value at most X def countNodes(root): # Initialize queue q = [] m = -sys.maxsize # Push root in queue with the # maximum value m q.append([ root, m ]) # Stores the count of good nodes count = 0 # Traverse all nodes while (len(q) > 0): # Store the front node of # the queue temp = q[0] q.pop(0) node = temp[0] num = temp[1] # Check is current node is # greater than the maximum # value in path from root to # the current node if (node.val >= num): count+=1 # Update the maximum value m m = max(node.val, num) # If left child is not null, # push it to queue with the # maximum value m if (node.left != None): q.append([ node.left, m ]) # If right child is not null, # push it to queue with the # maximum value m if (node.right != None): q.append([ node.right, m ]) # Returns the answer return count # Construct a Binary Tree root = None root = newNode(3) root.left = newNode(1) root.right = newNode(4) root.left.left = newNode(3) root.right.left = newNode(1) root.right.right = newNode(5) print(countNodes(root)) # This code is contributed by rameshtravel07.
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG {
// Node of the binary tree
class Node {
public int val;
public Node left, right;
public Node(int data)
{
val = data;
left = right = null;
}
}
// Function for creating new node
static Node newNode(int data)
{
// Allocate memory for new node
Node temp = new Node(data);
// Return the created node
return temp;
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
static int countNodes(Node root)
{
// Initialize queue
Queue q = new Queue();
int m = Int32.MinValue;
// Push root in queue with the
// maximum value m
q.Enqueue(new Tuple<Node, int>(root, m));
// Stores the count of good nodes
int count = 0;
// Traverse all nodes
while (q.Count > 0) {
// Store the front node of
// the queue
Tuple<Node, int> temp = (Tuple<Node, int>)q.Peek();
q.Dequeue();
Node node = temp.Item1;
int num = temp.Item2;
// Check is current node is
// greater than the maximum
// value in path from root to
// the current node
if (node.val >= num)
count++;
// Update the maximum value m
m = Math.Max(node.val, num);
// If left child is not null,
// push it to queue with the
// maximum value m
if (node.left != null)
q.Enqueue(new Tuple<Node, int>(node.left, m));
// If right child is not null,
// push it to queue with the
// maximum value m
if (node.right != null)
q.Enqueue(new Tuple<Node, int>(node.right, m));
}
// Returns the answer
return count;
}
// Driver code
static void Main()
{
// Construct a Binary Tree
Node root = null;
root = newNode(3);
root.left = newNode(1);
root.right = newNode(4);
root.left.left = newNode(3);
root.right.left = newNode(1);
root.right.right = newNode(5);
Console.Write(countNodes(root));
}
}
// This code is contributed by decode2207.
Javascript
<script>
// JavaScript program for the above approach
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.val = data;
}
}
// Function for creating new node
function newNode(data)
{
// Allocate memory for new node
let temp = new Node(data);
// Return the created node
return temp;
}
// Function to perform the DFS Traversal
// to find the number of paths having
// root to node X has value at most X
function countNodes(root)
{
// Initialize queue
let q = [];
let m = Number.MIN_VALUE;
// Push root in queue with the
// maximum value m
q.push([ root, m ]);
// Stores the count of good nodes
let count = 0;
// Traverse all nodes
while (q.length > 0) {
// Store the front node of
// the queue
let temp = q[0];
q.shift();
let node = temp[0];
let num = temp[1];
// Check is current node is
// greater than the maximum
// value in path from root to
// the current node
if (node.val >= num)
count++;
// Update the maximum value m
m = Math.max(node.val, num);
// If left child is not null,
// push it to queue with the
// maximum value m
if (node.left)
q.push([ node.left, m ]);
// If right child is not null,
// push it to queue with the
// maximum value m
if (node.right)
q.push([ node.right, m ]);
}
// Returns the answer
return count;
}
// Construct a Binary Tree
let root = null;
root = newNode(3);
root.left = newNode(1);
root.right = newNode(4);
root.left.left = newNode(3);
root.right.left = newNode(1);
root.right.right = newNode(5);
document.write(countNodes(root));
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Rohit_prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA