Dado un árbol binario que consta de N Nodes, la tarea de encontrar el promedio máximo de valores de los Nodes de cualquier subárbol.
Ejemplos:
Entrada: 5
/ \
3 8
Salida: 8
Explicación:
Promedio de valores del subárbol del Node 5 = (5 + 3 + 8) / 3 = 5.33
Promedio de valores del subárbol del Node 3 = 3 / 1 = 3
Promedio de valores del subárbol del Node 8 = 8 / 1 = 8.Entrada: 20
/ \
12 18
/ \ / \
11 3 15 8
Salida: 15
Explicación: El promedio de valores del subárbol del Node 15 es el máximo.
Enfoque: El problema dado es similar al de encontrar la mayor suma de subárboles en un árbol . La idea es utilizar la técnica transversal DFS . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, respuesta con 0 para almacenar el resultado.
- Defina una función maxAverage() para DFS transversal .
- Inicialice dos variables, sum para almacenar la suma de su subárbol y count para almacenar el número de Nodes en su subárbol, con 0 .
- Recorra los Nodes secundarios del Node actual y llame a maxAverage() para su Node secundario, e incremente la suma por la suma del subárbol del Node secundario y cuente por el total de Nodes en el Node secundario
- Incrementa la suma por el valor del Node actual y cuenta por 1 .
- Tome el máximo de ans y sum/count y guárdelo en ans .
- Finalmente, devuelve un par de {sum, count} .
- Imprime el promedio máximo obtenido como ans .
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val;
vector<TreeNode*> children;
TreeNode(int v)
{
val = v;
}
};
// Stores the result
double ans = 0.0;
// Function for finding maximum
// subtree average
vector<int> MaxAverage(TreeNode* root)
{
// Checks if current node is not
// NULL and doesn't have any children
if (root != NULL && root->children.size() == 0)
{
ans = max(ans, (root->val) * (1.0));
return {root->val, 1};
}
// Stores sum of its subtree in index 0
// and count number of nodes in index 1
vector<int> childResult (2);
// Traverse all children of the current node
for(TreeNode *child : root->children)
{
// Recursively calculate max average
// of subtrees among its children
vector<int> childTotal = MaxAverage(child);
// Increment sum by sum
// of its child's subtree
childResult[0] = childResult[0] + childTotal[0];
// Increment number of nodes
// by its child's node
childResult[1] = childResult[1] + childTotal[1];
}
// Increment sum by current node's value
int sum = childResult[0] + root->val;
// Increment number of
// nodes by one
int count = childResult[1] + 1;
// Take maximum of ans and
// current node's average
ans = max(ans, sum / count * 1.0);
// Finally return pair of {sum, count}
return{sum, count};
}
// Driver Code
int main()
{
// Given tree
TreeNode *root = new TreeNode(20);
TreeNode *left = new TreeNode(12);
TreeNode *right = new TreeNode(18);
root->children.push_back(left);
root->children.push_back(right);
left->children.push_back(new TreeNode(11));
left->children.push_back(new TreeNode(3));
right->children.push_back(new TreeNode(15));
right->children.push_back(new TreeNode(8));
// Function call
MaxAverage(root);
// Print answer
printf("%0.1f\n", ans);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
// Structure of the Tree node
class TreeNode {
public int val;
public List<TreeNode> children;
public TreeNode(int v)
{
val = v;
children = new ArrayList<TreeNode>();
}
}
class GFG {
// Stores the result
static double ans = 0.0;
// Function for finding maximum
// subtree average
public static double[] MaxAverage(
TreeNode root)
{
// Checks if current node is not
// null and doesn't have any children
if (root.children != null
&& root.children.size() == 0) {
ans = Math.max(ans, root.val);
return new double[] { root.val, 1 };
}
// Stores sum of its subtree in index 0
// and count number of nodes in index 1
double[] childResult = new double[2];
// Traverse all children of the current node
for (TreeNode child : root.children) {
// Recursively calculate max average
// of subtrees among its children
double[] childTotal
= MaxAverage(child);
// Increment sum by sum
// of its child's subtree
childResult[0]
= childResult[0] + childTotal[0];
// Increment number of nodes
// by its child's node
childResult[1]
= childResult[1] + childTotal[1];
}
// Increment sum by current node's value
double sum = childResult[0] + root.val;
// Increment number of
// nodes by one
double count = childResult[1] + 1;
// Take maximum of ans and
// current node's average
ans = Math.max(ans, sum / count);
// Finally return pair of {sum, count}
return new double[] { sum, count };
}
// Driver Code
public static void main(String[] args)
{
// Given tree
TreeNode root = new TreeNode(20);
TreeNode left = new TreeNode(12);
TreeNode right = new TreeNode(18);
root.children.add(left);
root.children.add(right);
left.children.add(new TreeNode(11));
left.children.add(new TreeNode(3));
right.children.add(new TreeNode(15));
right.children.add(new TreeNode(8));
// Function call
MaxAverage(root);
// Print answer
System.out.println(ans);
}
}
Python3
# Python3 program for the above approach
# Stores the result
ans = 0.0
class TreeNode:
def __init__ (self, val):
self.val = val
self.children = []
# Function for finding maximum
# subtree average
def MaxAverage(root):
global ans
# Checks if current node is not
# None and doesn't have any children
if (root != None and len(root.children) == 0):
ans = max(ans, (root.val))
return [root.val, 1]
# Stores sum of its subtree in index 0
# and count number of nodes in index 1
childResult = [0 for i in range(2)]
# Traverse all children of the current node
for child in root.children:
# Recursively calculate max average
# of subtrees among its children
childTotal = MaxAverage(child)
# Increment sum by sum
# of its child's subtree
childResult[0] = childResult[0] + childTotal[0]
# Increment number of nodes
# by its child's node
childResult[1] = childResult[1] + childTotal[1]
# Increment sum by current node's value
sum = childResult[0] + root.val
# Increment number of
# nodes by one
count = childResult[1] + 1
# Take maximum of ans and
# current node's average
ans = max(ans, sum / count)
# Finally return pair of {sum, count}
return [sum, count]
# Driver Code
if __name__ == '__main__':
# Given tree
root = TreeNode(20)
left = TreeNode(12)
right = TreeNode(18)
root.children.append(left)
root.children.append(right)
left.children.append(TreeNode(11))
left.children.append(TreeNode(3))
right.children.append(TreeNode(15))
right.children.append(TreeNode(8))
# Function call
MaxAverage(root)
# Print answer
print(ans * 1.0)
# This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Globalization;
public class TreeNode
{
public int val;
public List<TreeNode> children;
public TreeNode(int v)
{
val = v;
children = new List<TreeNode>();
}
}
public class GFG
{
// Stores the result
static double ans = 0.0;
// Function for finding maximum
// subtree average
public static double[] MaxAverage( TreeNode root)
{
// Checks if current node is not
// null and doesn't have any children
if (root.children != null
&& root.children.Count == 0)
{
ans = Math.Max(ans, root.val);
return new double[] { root.val, 1 };
}
// Stores sum of its subtree in index 0
// and count number of nodes in index 1
double[] childResult = new double[2];
// Traverse all children of the current node
foreach (TreeNode child in root.children)
{
// Recursively calculate max average
// of subtrees among its children
double[] childTotal
= MaxAverage(child);
// Increment sum by sum
// of its child's subtree
childResult[0]
= childResult[0] + childTotal[0];
// Increment number of nodes
// by its child's node
childResult[1]
= childResult[1] + childTotal[1];
}
// Increment sum by current node's value
double sum = childResult[0] + root.val;
// Increment number of
// nodes by one
double count = childResult[1] + 1;
// Take maximum of ans and
// current node's average
ans = Math.Max(ans, sum / count);
// Finally return pair of {sum, count}
return new double[] { sum, count };
}
// Driver code
static public void Main ()
{
// Given tree
TreeNode root = new TreeNode(20);
TreeNode left = new TreeNode(12);
TreeNode right = new TreeNode(18);
root.children.Add(left);
root.children.Add(right);
left.children.Add(new TreeNode(11));
left.children.Add(new TreeNode(3));
right.children.Add(new TreeNode(15));
right.children.Add(new TreeNode(8));
// Function call
MaxAverage(root);
// Print answer
NumberFormatInfo setPrecision = new NumberFormatInfo();
setPrecision.NumberDecimalDigits = 1;
Console.WriteLine(ans.ToString("N", setPrecision));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for the above approach
// Structure of the Tree node
class TreeNode
{
constructor(v)
{
this.val = v;
this.children = [];
}
}
// Stores the result
let ans = 0.0;
// Function for finding maximum
// subtree average
function MaxAverage(root)
{
// Checks if current node is not
// null and doesn't have any children
if (root.children != null
&& root.children.length == 0)
{
ans = Math.max(ans, root.val);
return [ root.val, 1 ];
}
// Stores sum of its subtree in index 0
// and count number of nodes in index 1
let childResult = new Array(2);
for(let i=0;i<childResult.length;i++)
{
childResult[i] = 0;
}
// Traverse all children of the current node
for (let child = 0; child < root.children.length; child++)
{
// Recursively calculate max average
// of subtrees among its children
let childTotal
= MaxAverage(root.children[child]);
// Increment sum by sum
// of its child's subtree
childResult[0]
= childResult[0] + childTotal[0];
// Increment number of nodes
// by its child's node
childResult[1]
= childResult[1] + childTotal[1];
}
// Increment sum by current node's value
let sum = childResult[0] + root.val;
// Increment number of
// nodes by one
let count = childResult[1] + 1;
// Take maximum of ans and
// current node's average
ans = Math.max(ans, sum / count);
// Finally return pair of {sum, count}
return [ sum, count ];
}
// Driver Code
// Given tree
let root = new TreeNode(20);
let left = new TreeNode(12);
let right = new TreeNode(18);
root.children.push(left);
root.children.push(right);
left.children.push(new TreeNode(11));
left.children.push(new TreeNode(3));
right.children.push(new TreeNode(15));
right.children.push(new TreeNode(8));
// Function call
MaxAverage(root);
// Print answer
document.write(ans.toFixed(1));
// This code is contributed by unknown2108
</script>
Producción:
15.0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shrutis2000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA