Dado un valor K y un árbol binario , la tarea es encontrar el número de subárboles que tienen OR bit a bit de todos sus elementos igual a K.
Ejemplos:
Input: K = 5, Tree = 2
/ \
1 1
/ \ \
10 5 4
Output: 2
Explanation:
Subtree 1:
5
It has only one element i.e. 5.
So bitwise OR of subtree = 5
Subtree 2:
1
\
4
it has 2 elements and bitwise OR of them is also 5
Input: K = 3, Tree = 4
/ \
3 9
/ \
2 2
Output: 1
Acercarse:
- Atraviese el árbol de forma recursiva utilizando el recorrido de pedido anticipado.
- Para cada Node, siga calculando el OR bit a bit de su subárbol como:
OR bit a bit de su subárbol = (OR bit a bit del subárbol izquierdo del Node) | (OR bit a bit del subárbol derecho del Node) | (valor del Node)
- Si el OR bit a bit de cualquier subárbol es K, incremente la variable contador.
- Imprima el valor en el contador como el conteo requerido.
C++
// C++ program to find the count of
// subtrees in a Binary Tree
// having bitwise OR value K
#include <bits/stdc++.h>
using namespace std;
// A binary tree node
struct Node {
int data;
struct Node *left, *right;
};
// A utility function to
// allocate a new node
struct Node* newNode(int data)
{
struct Node* newNode = new Node;
newNode->data = data;
newNode->left
= newNode->right = NULL;
return (newNode);
}
// Recursive Function to compute the count
int rec(Node* root, int& res, int& k)
{
// Base Case:
// If node is NULL, return 0
if (root == NULL) {
return 0;
}
// Calculating the bitwise OR
// of the current subtree
int orr = root->data;
orr |= rec(root->left, res, k);
orr |= rec(root->right, res, k);
// Increment res
// if xr is equal to k
if (orr == k) {
res++;
}
// Return the bitwise OR value
// of the current subtree
return orr;
}
// Function to find the required count
int FindCount(Node* root, int K)
{
// Initialize result variable 'res'
int res = 0;
// Recursively traverse the tree
// and compute the count
rec(root, res, K);
// return the count 'res'
return res;
}
// Driver program
int main(void)
{
/*
2
/ \
1 1
/ \ \
10 5 4
*/
// Create the binary tree
// by adding nodes to it
struct Node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(1);
root->right->right = newNode(4);
root->left->left = newNode(10);
root->left->right = newNode(5);
int K = 5;
cout << FindCount(root, K);
return 0;
}
Java
// Java program to find the count of
// subtrees in a Binary Tree
// having bitwise OR value K
import java.io.*;
class GFG
{
// A binary tree node
static class Node
{
public int data;
public Node left, right;
};
static int res;
static int k;
// A utility function to
// allocate a new node
static Node newNode(int data)
{
Node newNode = new Node();
newNode.data = data;
newNode.left = null;
newNode.right = null;
return newNode;
}
static int rec(Node root)
{
// Base Case:
// If node is null, return 0
if (root == null)
{
return 0;
}
// Calculating the XOR
// of the current subtree
int xr = (root.data);
xr |= rec(root.left);
xr |= rec(root.right);
// Increment res
// if xr is equal to k
if (xr == k)
{
res++;
}
// Return the XOR value
// of the current subtree
return xr;
}
// Function to find the required count
static int findCount(Node root, int K)
{
// Initialize result variable 'res'
res = 0;
k = K;
// Recursively traverse the tree
// and compute the count
rec(root);
// Return the count 'res'
return res;
}
// Driver code
public static void main (String[] args)
{
/*
2
/ \
1 1
/ \ \
10 5 4
*/
// Create the binary tree
// by adding nodes to it
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(1);
root.right.right = newNode(4);
root.left.left =newNode(10);
root.left.right = newNode(5);
int K = 5;
System.out.println(findCount(root, K));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to find the count of # subtrees in a Binary Tree # having bitwise OR value K # A binary tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # A utility function to # allocate a new node def newNode(data): temp = Node(data) return temp # Recursive Function to compute the count def rec(root, res, k): # Base Case: # If node is NULL, return 0 if (root == None): return [0, res]; # Calculating the bitwise OR # of the current subtree orr = root.data; tmp, res = rec(root.left, res, k); orr |= tmp tmp, res = rec(root.right, res, k); orr |= tmp # Increment res # if xr is equal to k if (orr == k): res += 1 # Return the bitwise OR value # of the current subtree return orr, res; # Function to find the required count def FindCount(root, K): # Initialize result variable 'res' res = 0; # Recursively traverse the tree # and compute the count tmp,res = rec(root, res, K); # return the count 'res' return res; # Driver program if __name__=='__main__': ''' 2 / \ 1 1 / \ \ 10 5 4 ''' # Create the binary tree # by adding nodes to it root = newNode(2); root.left = newNode(1); root.right = newNode(1); root.right.right = newNode(4); root.left.left = newNode(10); root.left.right = newNode(5); K = 5; print(FindCount(root, K)) # This code is contributed by rutvik_56
C#
// C# program to find the count of
// subtrees in a Binary Tree
// having bitwise OR value K
using System;
class GFG{
// A binary tree node
class Node
{
public int data;
public Node left, right;
};
static int res;
static int k;
// A utility function to
// allocate a new node
static Node newNode(int data)
{
Node newNode = new Node();
newNode.data = data;
newNode.left= null;
newNode.right = null;
return newNode;
}
static int rec(Node root)
{
// Base Case:
// If node is null, return 0
if (root == null)
{
return 0;
}
// Calculating the XOR
// of the current subtree
int xr = (root.data);
xr |= rec(root.left);
xr |= rec(root.right);
// Increment res
// if xr is equal to k
if (xr == k)
{
res++;
}
// Return the XOR value
// of the current subtree
return xr;
}
// Function to find the required count
static int findCount(Node root, int K)
{
// Initialize result variable 'res'
res = 0;
k = K;
// Recursively traverse the tree
// and compute the count
rec(root);
// Return the count 'res'
return res;
}
// Driver code
public static void Main(String []args)
{
/*
2
/ \
1 1
/ \ \
10 5 4
*/
// Create the binary tree
// by adding nodes to it
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(1);
root.right.right = newNode(4);
root.left.left =newNode(10);
root.left.right = newNode(5);
int K = 5;
Console.WriteLine(findCount(root, K));
}
}
// This code is contributed by mohit kumar
Javascript
<script>
// Javascript program to find the count of
// subtrees in a Binary Tree having bitwise
// OR value K
// Structure of node
class Node
{
// Utility function to
// create a new node
constructor(key)
{
this.data = key;
this.left = this.right = null;
}
}
let res, k;
function rec(root)
{
// Base Case:
// If node is null, return 0
if (root == null)
{
return 0;
}
// Calculating the XOR
// of the current subtree
let xr = (root.data);
xr |= rec(root.left);
xr |= rec(root.right);
// Increment res
// if xr is equal to k
if (xr == k)
{
res++;
}
// Return the XOR value
// of the current subtree
return xr;
}
// Function to find the required count
function findCount(root, K)
{
// Initialize result variable 'res'
res = 0;
k = K;
// Recursively traverse the tree
// and compute the count
rec(root);
// Return the count 'res'
return res;
}
// Driver code
/*
2
/ \
1 1
/ \ \
10 5 4
*/
// Create the binary tree
// by adding nodes to it
let root = new Node(2);
root.left = new Node(1);
root.right = new Node(1);
root.right.right = new Node(4);
root.left.left =new Node(10);
root.left.right = new Node(5);
let K = 5;
document.write(findCount(root, K));
// This code is contributed by patel2127
</script>
Producción:
2
Complejidad de tiempo: como en el enfoque anterior, estamos iterando sobre cada Node solo una vez, por lo tanto, tomará O (N) tiempo donde N es el número de Nodes en el árbol binario.
Complejidad del espacio auxiliar: como en el enfoque anterior, no se usa espacio adicional, por lo tanto, la complejidad del espacio auxiliar será O(1) .