Dado un árbol binario que consta de N Nodes y dos números enteros positivos L y R, la tarea es encontrar el recuento de Nodes que tienen su valor en el rango [L, R] .
Ejemplos:
Entrada: Árbol en la imagen de abajo, L = 4, R = 15
Salida: 2
Explicación: Los Nodes en el árbol dado que se encuentran en el rango [4, 15] son {5, 10}.Entrada: Árbol en la imagen de abajo, L = 8, R = 20
Salida: 4
Enfoque: el problema dado se puede resolver realizando cualquier Tree Traversal y manteniendo el recuento de Nodes que tienen sus valores en el rango [L, R] . Este artículo utiliza un recorrido DFS .
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;
// Class for node of the Tree
class Node {
public:
int val;
Node *left, *right;
};
// Function to create a new Binary node
Node* newNode(int item)
{
Node* temp = new Node();
temp->val = item;
temp->left = temp->right = NULL;
// Return the newly created node
return temp;
}
// Function to find the count of
// nodes in the given tree with
// their value in the range [1, N]
int countRange(Node* root, int low,
int high, int count)
{
int val = 0;
// If root exists
if (root != NULL) {
val += root->val >= low
&& root->val <= high
? 1
: 0;
}
// Otherwise return
else {
return 0;
}
// Add count of current node,
// count in left subtree, and
// count in the right subtree
count = val
+ countRange(root->left,
low, high, count)
+ countRange(root->right,
low, high, count);
// Return Answer
return count;
}
// Driver Code
int main()
{
Node* root = NULL;
root = newNode(20);
root->left = newNode(2);
root->right = newNode(10);
root->right->left = newNode(2);
root->right->right = newNode(5);
int L = 4, R = 15;
cout << countRange(root, L, R, 0);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Class for node of the Tree
static class Node {
int val;
Node left, right;
};
// Function to create a new Binary node
static Node newNode(int item)
{
Node temp = new Node();
temp.val = item;
temp.left = temp.right = null;
// Return the newly created node
return temp;
}
// Function to find the count of
// nodes in the given tree with
// their value in the range [1, N]
static int countRange(Node root, int low,
int high, int count)
{
int val = 0;
// If root exists
if (root != null) {
val += root.val >= low
&& root.val <= high
? 1
: 0;
}
// Otherwise return
else {
return 0;
}
// Add count of current node,
// count in left subtree, and
// count in the right subtree
count = val
+ countRange(root.left,
low, high, count)
+ countRange(root.right,
low, high, count);
// Return Answer
return count;
}
// Driver Code
public static void main(String[] args)
{
Node root = null;
root = newNode(20);
root.left = newNode(2);
root.right = newNode(10);
root.right.left = newNode(2);
root.right.right = newNode(5);
int L = 4, R = 15;
System.out.print(countRange(root, L, R, 0));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for the above approach # Class for Node of the Tree class Node: def __init__(self, val): self.val = val; self.left = None; self.right = None; # Function to create a new Binary Node def newNode(item): temp = Node(item); # Return the newly created Node return temp; # Function to find the count of # Nodes in the given tree with # their value in the range [1, N] def countRange(root, low, high, count): val = 0; # If root exists if (root != None): val += 1 if(root.val >= low and root.val <= high) else 0; # Otherwise return else: return 0; # Add count of current Node, # count in left subtree, and # count in the right subtree count = val + countRange(root.left, low, high, count) + countRange(root.right, low, high, count); # Return Answer return count; # Driver Code if __name__ == '__main__': root = None; root = newNode(20); root.left = newNode(2); root.right = newNode(10); root.right.left = newNode(2); root.right.right = newNode(5); L = 4; R = 15; print(countRange(root, L, R, 0)); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
public class GFG{
// Class for node of the Tree
class Node {
public int val;
public Node left, right;
};
// Function to create a new Binary node
static Node newNode(int item)
{
Node temp = new Node();
temp.val = item;
temp.left = temp.right = null;
// Return the newly created node
return temp;
}
// Function to find the count of
// nodes in the given tree with
// their value in the range [1, N]
static int countRange(Node root, int low,
int high, int count)
{
int val = 0;
// If root exists
if (root != null) {
val += root.val >= low
&& root.val <= high
? 1
: 0;
}
// Otherwise return
else {
return 0;
}
// Add count of current node,
// count in left subtree, and
// count in the right subtree
count = val
+ countRange(root.left,
low, high, count)
+ countRange(root.right,
low, high, count);
// Return Answer
return count;
}
// Driver Code
public static void Main(String[] args)
{
Node root = null;
root = newNode(20);
root.left = newNode(2);
root.right = newNode(10);
root.right.left = newNode(2);
root.right.right = newNode(5);
int L = 4, R = 15;
Console.Write(countRange(root, L, R, 0));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Class for node of the Tree
class Node {
constructor(val1) {
this.val = val1;
this.left = null;
this.right = null;
}
};
// Function to find the count of
// nodes in the given tree with
// their value in the range [1, N]
function countRange(root, low,
high, count) {
let val = 0;
// If root exists
if (root != null) {
val += root.val >= low
&& root.val <= high
? 1
: 0;
}
// Otherwise return
else {
return 0;
}
// Add count of current node,
// count in left subtree, and
// count in the right subtree
count = val
+ countRange(root.left,
low, high, count)
+ countRange(root.right,
low, high, count);
// Return Answer
return count;
}
// Driver Code
let root = null;
root = new Node(20);
root.left = new Node(2);
root.right = new Node(10);
root.right.left = new Node(2);
root.right.right = new Node(5);
let L = 4, R = 15;
document.write(countRange(root, L, R, 0));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)