Dado un árbol binario con valores enteros positivos. Encuentre la suma máxima de Nodes tal que no podamos elegir dos niveles para calcular la suma
Examples:
Input : Tree
1
/ \
2 3
/
4
\
5
/
6
Output :11
Explanation: Total items we can take: {1, 4, 6}
or {2, 3, 5}. Max sum = 11.
Input : Tree
1
/ \
2 3
/ / \
4 5 6
/ \ / /
17 18 19 30
/ / \
11 12 13
Output :89
Explanation: Total items we can take: {2, 3, 17, 18,
19, 30} or {1, 4, 5, 6, 11, 12, 13}.
Max sum from first set = 89.
Explicación : sabemos que necesitamos obtener valores de elementos de niveles de árbol alternativos. Esto significa que si elegimos desde el nivel 1, la próxima elección será desde el nivel 3, luego el nivel 5 y así sucesivamente. Del mismo modo, si comenzamos desde el nivel 2, la próxima elección será desde el nivel 4, luego el nivel 6 y así sucesivamente. Entonces, en realidad necesitamos sumar recursivamente todos los nietos de un elemento en particular, ya que se garantiza que estarán en el nivel alternativo.
Sabemos que para cualquier Node de árbol, hay 4 nietos.
grandchild1 = root.left.left;
grandchild2 = root.left.right;
grandchild3 = root.right.left;
grandchild4 = root.right.right;
Podemos llamar recursivamente al método getSum() en el siguiente programa para encontrar la suma de estos hijos y sus nietos. Al final, solo necesitamos devolver la suma máxima obtenida al comenzar en el nivel 1 y comenzar en el nivel 2 .
C++
// C++ code for max sum with adjacent levels
// not allowed
#include<bits/stdc++.h>
using namespace std;
// Tree node class for Binary Tree
// representation
struct Node
{
int data;
Node* left, *right;
Node(int item)
{
data = item;
}
} ;
int getSum(Node* root) ;
// Recursive function to find the maximum
// sum returned for a root node and its
// grandchildren
int getSumAlternate(Node* root)
{
if (root == NULL)
return 0;
int sum = root->data;
if (root->left != NULL)
{
sum += getSum(root->left->left);
sum += getSum(root->left->right);
}
if (root->right != NULL)
{
sum += getSum(root->right->left);
sum += getSum(root->right->right);
}
return sum;
}
// Returns maximum sum with adjacent
// levels not allowed-> This function
// mainly uses getSumAlternate()
int getSum(Node* root)
{
if (root == NULL)
return 0;
// We compute sum of alternate levels
// starting first level and from second
// level->
// And return maximum of two values->
return max(getSumAlternate(root),
(getSumAlternate(root->left) +
getSumAlternate(root->right)));
}
// Driver function
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->right->left = new Node(4);
root->right->left->right = new Node(5);
root->right->left->right->left = new Node(6);
cout << (getSum(root));
return 0;
}
// This code is contributed by Arnab Kundu
Java
// Java code for max sum with adjacent levels
// not allowed
import java.util.*;
public class Main {
// Tree node class for Binary Tree
// representation
static class Node {
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
// Recursive function to find the maximum
// sum returned for a root node and its
// grandchildren
public static int getSumAlternate(Node root)
{
if (root == null)
return 0;
int sum = root.data;
if (root.left != null) {
sum += getSum(root.left.left);
sum += getSum(root.left.right);
}
if (root.right != null) {
sum += getSum(root.right.left);
sum += getSum(root.right.right);
}
return sum;
}
// Returns maximum sum with adjacent
// levels not allowed. This function
// mainly uses getSumAlternate()
public static int getSum(Node root)
{
if (root == null)
return 0;
// We compute sum of alternate levels
// starting first level and from second
// level.
// And return maximum of two values.
return Math.max(getSumAlternate(root),
(getSumAlternate(root.left) +
getSumAlternate(root.right)));
}
// Driver function
public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.right.left.right = new Node(5);
root.right.left.right.left = new Node(6);
System.out.println(getSum(root));
}
}
Python3
# Python3 code for max sum with adjacent # levels not allowed from collections import deque as queue # A BST node class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Recursive function to find the maximum # sum returned for a root node and its # grandchildren def getSumAlternate(root): if (root == None): return 0 sum = root.data if (root.left != None): sum += getSum(root.left.left) sum += getSum(root.left.right) if (root.right != None): sum += getSum(root.right.left) sum += getSum(root.right.right) return sum # Returns maximum sum with adjacent # levels not allowed. This function # mainly uses getSumAlternate() def getSum(root): if (root == None): return 0 # We compute sum of alternate levels # starting first level and from second # level. # And return maximum of two values. return max(getSumAlternate(root), (getSumAlternate(root.left) + getSumAlternate(root.right))) # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.right.left = Node(4) root.right.left.right = Node(5) root.right.left.right.left = Node(6) print(getSum(root)) # This code is contributed by mohit kumar 29
C#
// C# code for max sum with adjacent levels
// not allowed
using System;
class GFG
{
// Tree node class for Binary Tree
// representation
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
// Recursive function to find the maximum
// sum returned for a root node and its
// grandchildren
public static int getSumAlternate(Node root)
{
if (root == null)
return 0;
int sum = root.data;
if (root.left != null)
{
sum += getSum(root.left.left);
sum += getSum(root.left.right);
}
if (root.right != null)
{
sum += getSum(root.right.left);
sum += getSum(root.right.right);
}
return sum;
}
// Returns maximum sum with adjacent
// levels not allowed. This function
// mainly uses getSumAlternate()
public static int getSum(Node root)
{
if (root == null)
return 0;
// We compute sum of alternate levels
// starting first level and from second
// level.
// And return maximum of two values.
return Math.Max(getSumAlternate(root),
(getSumAlternate(root.left) +
getSumAlternate(root.right)));
}
// Driver code
public static void Main()
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.right.left.right = new Node(5);
root.right.left.right.left = new Node(6);
Console.WriteLine(getSum(root));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript code for max sum with
// adjacent levels not allowed
// Tree node class for Binary Tree
// representation
class Node
{
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
// Recursive function to find the maximum
// sum returned for a root node and its
// grandchildren
function getSumAlternate(root)
{
if (root == null)
return 0;
let sum = root.data;
if (root.left != null)
{
sum += getSum(root.left.left);
sum += getSum(root.left.right);
}
if (root.right != null)
{
sum += getSum(root.right.left);
sum += getSum(root.right.right);
}
return sum;
}
// Returns maximum sum with adjacent
// levels not allowed. This function
// mainly uses getSumAlternate()
function getSum(root)
{
if (root == null)
return 0;
// We compute sum of alternate levels
// starting first level and from second
// level.
// And return maximum of two values.
return Math.max(getSumAlternate(root),
(getSumAlternate(root.left) +
getSumAlternate(root.right)));
}
// Driver code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.right.left.right = new Node(5);
root.right.left.right.left = new Node(6);
document.write(getSum(root));
// This code is contributed by patel2127
</script>
Producción:
11
Complejidad de tiempo : O(n)
Ejercicio: intente imprimir la misma solución para un árbol n-ario en lugar de un árbol binario. El truco está en la representación del árbol.
Este artículo es una contribución de Ashish Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA