Cuente las rutas en un árbol binario que consta de Nodes en orden no decreciente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *