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