Dado un árbol binario , la tarea es encontrar la suma del subárbol más frecuente que se puede obtener considerando cada Node del árbol dado como la raíz del subárbol. Si existen más de una de esas sumas, imprímalas todas.
Ejemplos:
Entrada:
5
/ \
2 -4Salida: 2 -4 3
Explicación:
La suma de Nodes considerando 5 como la raíz del subárbol es 5 + 2 – 4 = 3.
La suma de Nodes considerando 2 como la raíz del subárbol es 2 = 2.
La suma de Nodes considerando – 4 como raíz del subárbol es -4 = -4.
Como todas las sumas tienen la misma frecuencia, imprima todas las sumas.Entrada:
4
/ \
2 -4Salida: 2
Explicación:
La suma de los Nodes que consideran 4 como la raíz del subárbol es 4 + 2 – 4 = 2.
La suma de los Nodes que consideran 2 como la raíz del subárbol es 2 = 2.
La suma de los Nodes que consideran -4 como la la raíz del subárbol es -4 = -4.
Ya que suma 2 tiene frecuencia máxima ( = 2). Por lo tanto, imprima el valor 2.
Enfoque: La idea de usar el DFS Traversal para el árbol dado para resolver el problema dado. Siga los pasos a continuación para resolver el problema:
- Cree dos mapas hash auxiliares M y F , donde M es un conjunto de claves enteras y las listas correspondientes, y F almacenará la frecuencia de cada número.
- Realice el DFS Traversal para el árbol dado y haga lo siguiente:
- Si el Node es NULL , devuelve 0 .
- Inicialice las variables izquierda y derecha que almacenan el valor de la suma de los Nodes del subárbol izquierdo y derecho del Node actual.
- Encuentre la suma de currentNode.value + left + right guárdela en una variable totalSum .
- Ahora actualice la frecuencia de totalSum en el mapa F .
- Actualice la frecuencia del valor F[totalSum] como totalSum en el mapa M .
- Devuelve el valor a totalSum de la función recursiva actual.
- Después de los pasos anteriores, imprima todos los elementos de la lista M.rbegin() .
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;
// Function to print the vector
void printVector(vector<int> v)
{
// Traverse vector c
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
}
// TreeNode class
class TreeNode {
public:
int val;
TreeNode *left, *right;
// Constructor
TreeNode(int data)
{
val = data;
left = NULL;
right = NULL;
}
};
// Function to insert node in the
// binary tree
void insert(TreeNode** root, int val)
{
// Initialize Queue
queue<TreeNode*> q;
// Push the node root
q.push(*root);
// While Q.size() is there
while (q.size()) {
// Get the front node
TreeNode* temp = q.front();
q.pop();
// If left is NULL
if (!temp->left) {
if (val)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}
else {
q.push(temp->left);
}
// If right is NULL
if (!temp->right) {
if (val)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}
else {
q.push(temp->right);
}
}
}
// Function to make the tree from
// given node values
TreeNode* buildTree(vector<int> v)
{
TreeNode* root = new TreeNode(v[0]);
// Traverse and insert node
for (int i = 1; i < v.size(); i++) {
insert(&root, v[i]);
}
return root;
}
// Utility function to find subtree
// sum with highest frequency of a
// particular node
int findsubTreeSumUtil(
TreeNode* node, map<int,
vector<int> >& mpp,
map<int, int>& frequency)
{
if (!node)
return 0;
// Recur for the left subtree
int left = findsubTreeSumUtil(
node->left, mpp, frequency);
// Recur for the right subtree
int right = findsubTreeSumUtil(
node->right, mpp, frequency);
// Stores sum of nodes of a subtree
int totalSum = node->val + left + right;
// Update the frequency
if (!frequency.count(totalSum)) {
mpp[1].push_back(totalSum);
frequency[totalSum] = 1;
}
else {
frequency[totalSum]++;
mpp[frequency[totalSum]].push_back(totalSum);
}
// Return the total sum
return totalSum;
}
// Function to find subtree sum with
// highest frequency of given tree
void findsubTreeSum(TreeNode* root)
{
// Store list of nodes attached to
// a particular node and frequency
// of visited nodes
map<int, vector<int> > mpp;
map<int, int> frequency;
// Base Case
if (!root) {
printVector({});
return;
}
// DFS function call
findsubTreeSumUtil(root, mpp, frequency);
// Print the vector
printVector(mpp.rbegin()->second);
}
// Driver Code
int main()
{
// Given nodes of the tree
vector<int> v = { 5, 2, -4 };
// Function call to build the tree
TreeNode* tree = buildTree(v);
// Function Call
findsubTreeSum(tree);
return 0;
}
Java
// Java program for the above approach
// Importing required classes
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;
public class GFG {
// Function to print the list
static void printVector(ArrayList<Integer> v)
{
// Traverse list
for (int i = 0; i < v.size(); i++) {
System.out.print(v.get(i) + " ");
}
}
// TreeNode class
static class TreeNode {
int val;
TreeNode left, right;
// Constructor
TreeNode(int data)
{
val = data;
left = null;
right = null;
}
}
// Function to insert node in the
// binary tree
static void insert(TreeNode root, int val)
{
// Initialize Queue
Queue<TreeNode> q = new LinkedList<TreeNode>();
// Push the node root
q.add(root);
// While queue is not empty
while (q.isEmpty() == false) {
// Get the front node
TreeNode temp = q.peek();
q.poll();
// If left is NULL
if (temp.left == null) {
temp.left = new TreeNode(val);
return;
}
else {
q.add(temp.left);
}
// If right is NULL
if (temp.right == null) {
temp.right = new TreeNode(val);
return;
}
else {
q.add(temp.right);
}
}
}
// Function to make the tree from
// given node values
static TreeNode buildTree(ArrayList<Integer> v)
{
TreeNode root = new TreeNode(v.get(0));
// Traverse and insert node
for (int i = 1; i < v.size(); i++) {
insert(root, v.get(i));
}
return root;
}
// Utility function to find subtree
// sum with highest frequency of a
// particular node
static int findsubTreeSumUtil(
TreeNode node,
TreeMap<Integer, ArrayList<Integer> > mpp,
HashMap<Integer, Integer> frequency)
{
if (node == null)
return 0;
// Recur for the left subtree
int left
= findsubTreeSumUtil(node.left, mpp, frequency);
// Recur for the right subtree
int right = findsubTreeSumUtil(node.right, mpp,
frequency);
// Stores sum of nodes of a subtree
int totalSum = node.val + left + right;
// Update the frequency
// If there is no node with sub-tree sum equal to
// totalSum It is the first occurrence of totalSum
// value
if (frequency.get(totalSum) == null) {
ArrayList<Integer> temp = mpp.get(1);
// If there is no sum which has occurred only
// once
if (temp == null)
temp = new ArrayList<Integer>();
temp.add(totalSum);
mpp.put(1, temp);
frequency.put(totalSum, 1);
}
// There is a node with sub-tree sum equal to
// totalSum
else {
frequency.put(totalSum,
frequency.get(totalSum) + 1);
// Get list of sum values which has
// occurrence equal to occurrence of totalSum
ArrayList<Integer> temp
= mpp.get(frequency.get(totalSum));
// If there is no sum which has occurrence
// equal to occurrence of totalSum
if (temp == null)
temp = new ArrayList<Integer>();
temp.add(totalSum);
mpp.put(frequency.get(totalSum), temp);
}
// Return the total sum
return totalSum;
}
// Function to find subtree sum with
// highest frequency of given tree
static void findsubTreeSum(TreeNode root)
{
// Store list of nodes attached to
// a particular node and frequency
// of visited nodes
TreeMap<Integer, ArrayList<Integer> > mpp
= new TreeMap<Integer, ArrayList<Integer> >();
HashMap<Integer, Integer> frequency
= new HashMap<Integer, Integer>();
// Base Case
if (root == null) {
return;
}
// DFS function call
findsubTreeSumUtil(root, mpp, frequency);
// Print the list of most-frequent subtree sum
printVector(mpp.lastEntry().getValue());
}
// Driver Code
public static void main(String args[])
{
// Given nodes of the tree
ArrayList<Integer> v = new ArrayList<Integer>();
v.addAll(Arrays.asList(5, 2, -4));
// Function call to build the tree
TreeNode tree = buildTree(v);
// Function Call
findsubTreeSum(tree);
}
}
// This code is contributed by jainlovely450
Producción:
2 -4 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA