Dado un árbol binario de N Nodes. Cuenta la frecuencia de un entero K en el árbol binario.
Ejemplos:
Entrada: N = 7, K = 2
1
/ \
2 3
/ \ / \
4 2 2 5
Salida: 3
Explicación : 2 aparece 3 veces en el árbol.Entrada: N = 6, K = 5
1
/ \
4 5
/ \ / \
5 6 2 4
Salida: 2
Explicación : 5 aparece 2 veces en el árbol.
Enfoque : La solución al problema se basa en el recorrido del árbol binario dado. Siga los pasos como se muestra a continuación:
- Realizar un recorrido en orden del árbol binario dado
- Para cada Node en el árbol, verifique si es igual a K o no
- Si es igual a K , incremente el conteo requerido en 1 .
- Al final, devuelva la cuenta final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Function for inorder tree traversal
int countOccurrence(struct Node* root, int K)
{
stack<Node*> s;
Node* curr = root;
// Variable for counting frequency of K
int count = 0;
while (curr != NULL || s.empty() == false) {
// Reach the left most Node
// of the curr Node
while (curr != NULL) {
// Place pointer to a tree node
// on the stack before
// traversing the node's
// left subtree
s.push(curr);
curr = curr->left;
}
// Current must be NULL at this point
curr = s.top();
s.pop();
// Increment count if element = K
if (curr->data == K)
count++;
// Traverse the right subtree
curr = curr->right;
}
return count;
}
// Driver code
int main()
{
// Binary tree as shown in example
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(2);
root->left->left = new Node(4);
root->left->right = new Node(2);
int K = 2;
// Function call
int ans = countOccurrence(root, K);
cout << ans << endl;
return 0;
}
Java
// JAVA code to implement the approach
import java.util.*;
// Structure of a tree node
class Node {
int data;
Node left;
Node right;
Node(int data)
{
this.data = data;
left = right = null;
}
}
class GFG {
// Function for inorder tree traversal
public static int countOccurrence(Node root, int K)
{
Stack<Node> s = new Stack<Node>();
Node curr = root;
// Variable for counting frequency of K
int count = 0;
while (curr != null || s.empty() == false) {
// Reach the left most Node
// of the curr Node
while (curr != null) {
// Place pointer to a tree node
// on the stack before
// traversing the node's
// left subtree
s.push(curr);
curr = curr.left;
}
// Current must be NULL at this point
curr = s.peek();
s.pop();
// Increment count if element = K
if (curr.data == K)
count++;
// Traverse the right subtree
curr = curr.right;
}
return count;
}
// Driver code
public static void main(String[] args)
{
// Binary tree as shown in example
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(4);
root.left.right = new Node(2);
int K = 2;
// Function call
int ans = countOccurrence(root, K);
System.out.println(ans);
}
}
// This code is contributed by Taranpreet
Python3
# Python code for the above approach # Structure of a tree node class Node: def __init__(self,d): self.data = d self.left = None self.right = None # Function for inorder tree traversal def countOccurrence(root, K): s = [] curr = root # Variable for counting frequency of K count = 0 while (curr != None or len(s) != 0): # Reach the left most Node # of the curr Node while (curr != None): # Place pointer to a tree node # on the stack before # traversing the node's # left subtree s.append(curr) curr = curr.left # Current must be None at this point curr = s[len(s) - 1] s.pop() # Increment count if element = K if (curr.data == K): count += 1 # Traverse the right subtree curr = curr.right return count # Driver code # Binary tree as shown in example root = Node(1) root.left = Node(2) root.right = Node(2) root.left.left = Node(4) root.left.right = Node(2) K = 2 # Function call ans = countOccurrence(root, K) print(ans) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
// Structure of a tree node
public class Node {
public int data;
public Node left;
public Node right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
class GFG {
// Function for inorder tree traversal
public static int countOccurrence(Node root, int K)
{
Stack<Node> s = new Stack<Node> ();
Node curr = root;
// Variable for counting frequency of K
int count = 0;
while (curr != null || s.Count!=0) {
// Reach the left most Node
// of the curr Node
while (curr != null) {
// Place pointer to a tree node
// on the stack before
// traversing the node's
// left subtree
s.Push(curr);
curr = curr.left;
}
// Current must be NULL at this point
curr = s.Peek();
s.Pop();
// Increment count if element = K
if (curr.data == K)
count++;
// Traverse the right subtree
curr = curr.right;
}
return count;
}
// Driver Code
public static void Main () {
// Build a tree
// Binary tree as shown in example
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(4);
root.left.right = new Node(2);
int K = 2;
// Function call
int ans = countOccurrence(root, K);
Console.WriteLine(ans);
}
}
// This code is contributed by jana_sayantan.
Javascript
<script>
// JavaScript code for the above approach
// Structure of a tree node
class Node {
constructor(d) {
this.data = d;
this.left = null;
this.right = null;
}
};
// Function for inorder tree traversal
function countOccurrence(root, K) {
let s = [];
let curr = root;
// Variable for counting frequency of K
let count = 0;
while (curr != null || s.length != 0) {
// Reach the left most Node
// of the curr Node
while (curr != null) {
// Place pointer to a tree node
// on the stack before
// traversing the node's
// left subtree
s.push(curr);
curr = curr.left;
}
// Current must be null at this point
curr = s[s.length - 1];
s.pop();
// Increment count if element = K
if (curr.data == K)
count++;
// Traverse the right subtree
curr = curr.right;
}
return count;
}
// Driver code
// Binary tree as shown in example
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(4);
root.left.right = new Node(2);
let K = 2;
// Function call
let ans = countOccurrence(root, K);
document.write(ans + '<br>')
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal : O(N)
Espacio auxiliar: O(N)