Cuente los Nodes que tienen el valor más pequeño en la ruta desde la raíz hasta sí mismo en un árbol binario

Dado un árbol binario , la tarea es contar el número de Nodes en el árbol binario dado de modo que la ruta desde la raíz hasta ese Node contenga un Node con un valor mayor o igual que ese Node.

Ejemplos:

Input:
               6
             /   \
            7     4
           / \   / \
          3   7 1   2

Output: 5
Explanation:
Root node 6 is considered as its the only node 
in the path from root to itself.
Node 4 has the minimum value in it's path 6->4.
Node 1 has the minimum value in it's path 6->4->1.
Node 2 has the minimum value in it's path 6->4->2.
Node 3 has the minimum value in it's path 6->7->3.

Input:
               8
             /   \
            6     5
           / \   / \
          6   7 3   9

Output: 5
Explanation:
Root node 8 is considered as its the only node
in the path from root to itself.
Node 6 has the minimum value in it's path 8->6.
Node 6 has the minimum value in it's path 8->6->6.
Node 5 has the minimum value in it's path 8->5.
Node 3 has the minimum value in it's path 8->5->3.

Enfoque: la idea es hacer un recorrido de pedido anticipado en el árbol binario dado. Siga los pasos a continuación para resolver el problema:

  1. Cree una función para calcular el número de Nodes que satisfacen las condiciones dadas.
  2. Si el Node actual es NULL, regrese al Node anterior.
  3. Utilice una variable minNodeVal para almacenar el valor de Node mínimo a lo largo de la ruta desde la raíz hasta el Node actual.
  4. Si el valor del Node actual es menor o igual que minNodeVal , aumente el recuento final en 1 y actualice el valor de minNodeVal .
  5. Llame a la función para el hijo izquierdo y derecho del Node actual y repita este proceso para cada Node para obtener el recuento total de los Nodes requeridos.

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;
 
// Structure of a tree node
struct Node {
    int key;
    Node *left, *right;
};
 
// Function to create new tree node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Function to find the total
// number of required nodes
void countReqNodes(Node* root,
                   int minNodeVal, int& ans)
{
    // If current node is null then
    // return to the parent node
    if (root == NULL)
        return;
 
    // Check if current node value is
    // less than or equal to minNodeVal
    if (root->key <= minNodeVal) {
 
        // Update the value of minNodeVal
        minNodeVal = root->key;
 
        // Update the count
        ans++;
    }
 
    // Go to the left subtree
    countReqNodes(root->left,
                  minNodeVal, ans);
 
    // Go to the right subtree
    countReqNodes(root->right,
                  minNodeVal, ans);
}
 
// Driver Code
int main()
{
    /* Binary Tree creation
               8
             /   \
            /     \
           6       5
          / \     /  \
         /   \   /    \
        6     7 3      9
    */
 
    Node* root = newNode(8);
    root->left = newNode(6);
    root->right = newNode(5);
    root->left->left = newNode(6);
    root->left->right = newNode(7);
    root->right->left = newNode(3);
    root->right->right = newNode(9);
 
    int ans = 0, minNodeVal = INT_MAX;
 
    // Function Call
    countReqNodes(root, minNodeVal, ans);
 
    // Print the result
    cout << ans;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Structure of a tree node
static class Node
{
    int key;
    Node left, right;
};
 
// Function to create new tree node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return temp;
}
static int ans;
 
// Function to find the total
// number of required nodes
static void countReqNodes(Node root,
                          int minNodeVal)
{
     
    // If current node is null then
    // return to the parent node
    if (root == null)
        return;
 
    // Check if current node value is
    // less than or equal to minNodeVal
    if (root.key <= minNodeVal)
    {
         
        // Update the value of minNodeVal
        minNodeVal = root.key;
 
        // Update the count
        ans++;
    }
 
    // Go to the left subtree
    countReqNodes(root.left,
                  minNodeVal);
 
    // Go to the right subtree
    countReqNodes(root.right,
                  minNodeVal);
}
 
// Driver Code
public static void main(String[] args)
{
     
    /* Binary Tree creation
               8
             /   \
            /     \
           6       5
          / \     /  \
         /   \   /    \
        6     7 3      9
    */
 
    Node root = newNode(8);
    root.left = newNode(6);
    root.right = newNode(5);
    root.left.left = newNode(6);
    root.left.right = newNode(7);
    root.right.left = newNode(3);
    root.right.right = newNode(9);
 
    int  minNodeVal = Integer.MAX_VALUE;
    ans = 0;
     
    // Function Call
    countReqNodes(root, minNodeVal);
     
    // Print the result
    System.out.print(ans);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
import sys
 
ans = 0
 
# Class of a tree node
class Node:
     
    def __init__(self, key):
         
        self.key = key
        self.left = None
        self.right = None
 
# Function to find the total
# number of required nodes
def countReqNodes(root, minNodeVal):
     
    global ans
 
    # If current node is null then
    # return to the parent node
    if root == None:
        return
     
    # Check if current node value is
    # less than or equal to minNodeVal   
    if root.key <= minNodeVal:
         
        # Update the value of minNodeVal
        minNodeVal = root.key
 
        # Update the count
        ans += 1
         
    # Go to the left subtree   
    countReqNodes(root.left, minNodeVal)
 
    # Go to the right subtree
    countReqNodes(root.right, minNodeVal)
 
# Driver Code
if __name__ == '__main__':
     
     # Binary Tree creation
     #           8
     #         /   \
     #        /     \
     #       6       5
     #      / \     /  \
     #     /   \   /    \
     #    6     7 3      9
     #
 
    root = Node(8)
 
    root.left = Node(6)
    root.right = Node(5)
    root.left.left = Node(6)
    root.left.right = Node(7)
    root.right.left = Node(3)
    root.right.right = Node(9)
 
    minNodeVal = sys.maxsize
     
    # Function Call
    countReqNodes(root, minNodeVal)
     
    # Print the result
    print(ans)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Structure of a tree node
public class Node
{
    public int key;
    public Node left, right;
};
 
// Function to create new tree node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return temp;
}
 
static int ans;
 
// Function to find the total
// number of required nodes
static void countReqNodes(Node root,
                          int minNodeVal)
{
     
    // If current node is null then
    // return to the parent node
    if (root == null)
        return;
 
    // Check if current node value is
    // less than or equal to minNodeVal
    if (root.key <= minNodeVal)
    {
         
        // Update the value of minNodeVal
        minNodeVal = root.key;
 
        // Update the count
        ans++;
    }
 
    // Go to the left subtree
    countReqNodes(root.left,
                  minNodeVal);
 
    // Go to the right subtree
    countReqNodes(root.right,
                  minNodeVal);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    /* Binary Tree creation
               8
             /   \
            /     \
           6       5
          / \     /  \
         /   \   /    \
        6     7 3      9
    */
 
    Node root = newNode(8);
    root.left = newNode(6);
    root.right = newNode(5);
    root.left.left = newNode(6);
    root.left.right = newNode(7);
    root.right.left = newNode(3);
    root.right.right = newNode(9);
 
    int  minNodeVal = int.MaxValue;
    ans = 0;
     
    // Function Call
    countReqNodes(root, minNodeVal);
     
    // Print the result
    Console.Write(ans);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program for the above approach
 
// Structure of tree node
class Node
{
    constructor(key)
    {
         
        this.left = null;
        this.right = null;
        this.key = key;
    }
}
 
// Function to create new tree node
function newNode(key)
{
    let temp = new Node(key);
    return temp;
}
 
let ans;
 
// Function to find the total
// number of required nodes
function countReqNodes(root, minNodeVal)
{
     
    // If current node is null then
    // return to the parent node
    if (root == null)
        return;
 
    // Check if current node value is
    // less than or equal to minNodeVal
    if (root.key <= minNodeVal)
    {
         
        // Update the value of minNodeVal
        minNodeVal = root.key;
 
        // Update the count
        ans++;
    }
 
    // Go to the left subtree
    countReqNodes(root.left,
                  minNodeVal);
 
    // Go to the right subtree
    countReqNodes(root.right,
                  minNodeVal);
}
 
// Driver code
 
/* Binary Tree creation
           8
         /   \
        /     \
       6       5
      / \     /  \
     /   \   /    \
    6     7 3      9
*/
let root = newNode(8);
root.left = newNode(6);
root.right = newNode(5);
root.left.left = newNode(6);
root.left.right = newNode(7);
root.right.left = newNode(3);
root.right.right = newNode(9);
 
let  minNodeVal = Number.MAX_VALUE;
ans = 0;
  
// Function Call
countReqNodes(root, minNodeVal);
  
// Print the result
document.write(ans);
 
// This code is contributed by suresh07
 
</script>
Producción: 

5

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por kundudinesh007 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 *