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:
- Cree una función para calcular el número de Nodes que satisfacen las condiciones dadas.
- Si el Node actual es NULL, regrese al Node anterior.
- 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.
- Si el valor del Node actual es menor o igual que minNodeVal , aumente el recuento final en 1 y actualice el valor de minNodeVal .
- 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