Dado un valor K y un árbol binario , la tarea es encontrar el número de subárboles que tienen XOR de todos sus elementos igual a K.
Ejemplos:
Input K = 5, Tree =
2
/ \
1 9
/ \
10 5
Output: 2
Explanation:
Subtree 1:
5
It has only one element i.e. 5.
So XOR of subtree = 5
Subtree 1:
2
/ \
1 9
/ \
10 5
It has elements 2, 1, 9, 10, 5.
So XOR of subtree = 2 ^ 1 ^ 9 ^ 10 ^ 5 = 5
Input K = 3, Tree =
4
/ \
3 9
/ \
2 2
Output: 1
Explanation
Subtree:
3
/ \
2 2
It has elements 3, 2, 2.
So XOR of subtree = 3 ^ 2 ^ 2 = 3
Acercarse
- Atraviese el árbol de forma recursiva mediante pre-order traversal .
- Para cada Node, siga calculando el XOR de su subárbol como:
XOR de su subárbol = (XOR del subárbol izquierdo del Node) ^ (XOR del subárbol derecho de los Nodes) ^ (valor del Node)
- Si el XOR de cualquier subárbol es K, incremente la variable de contador.
- Imprime el valor en el contador como el conteo requerido
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the count of
// subtrees in a Binary Tree
// having XOR 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);
}
int rec(Node* root, int& res, int& k)
{
// 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, res, k);
xr ^= rec(root->right, res, k);
// 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
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 9
/ \
10 5
*/
// Create the binary tree
// by adding nodes to it
struct Node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(9);
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 XOR value K
import java.util.*;
class GFG{
// A binary tree node
static class Node
{
int data;
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);//^rec(root.left)^rec(root.right);
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 program
public static void main(String args[])
{
/*
2
/ \
1 9
/ \
10 5
*/
// Create the binary tree
// by adding nodes to it
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(9);
root.left.left =newNode(10);
root.left.right = newNode(5);
int K = 5;
System.out.println(findCount(root, K));
}
}
// This code is contributed by AbhiThakur
Python3
# Python3 program to find the count of # subtrees in a Binary Tree # having XOR 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): newNode = Node(data) return newNode def rec(root, res, k): # Base Case: # If node is None, return 0 if (root == None): return [0, res]; # Calculating the XOR # of the current subtree xr = root.data; tmp,res = rec(root.left, res, k); xr^=tmp tmp,res = rec(root.right, res, k); xr^=tmp # Increment res # if xr is equal to k if (xr == k): res += 1 # Return the XOR value # of the current subtree return xr, 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 9 / \ 10 5 ''' # Create the binary tree # by adding nodes to it root = newNode(2); root.left = newNode(1); root.right = newNode(9); 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 XOR value K
using System;
public 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);//^rec(root.left)^rec(root.right);
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 program
public static void Main(String []args)
{
/*
2
/ \
1 9
/ \
10 5
*/
// Create the binary tree
// by adding nodes to it
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(9);
root.left.left =newNode(10);
root.left.right = newNode(5);
int K = 5;
Console.WriteLine(findCount(root, K));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program to find the count of
// subtrees in a Binary Tree
// having XOR value K
// A binary tree node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
var res = 0;
var k = 0;
// A utility function to
// allocate a new node
function newNode(data)
{
var newNode = new Node();
newNode.data = data;
newNode.left= null;
newNode.right = null;
return newNode;
}
function rec(root)
{
// Base Case:
// If node is null, return 0
if (root == null) {
return 0;
}
// Calculating the XOR
// of the current subtree
var xr = (root.data);//^rec(root.left)^rec(root.right);
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 program
/*
2
/ \
1 9
/ \
10 5
*/
// Create the binary tree
// by adding nodes to it
var root = newNode(2);
root.left = newNode(1);
root.right = newNode(9);
root.left.left =newNode(10);
root.left.right = newNode(5);
var K = 5;
document.write(findCount(root, K));
</script>
Producción:
2
Análisis de rendimiento:
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 utiliza espacio adicional, por lo tanto, la complejidad del espacio auxiliar será O(1) .