Dado un árbol binario con un valor asociado con cada Node, necesitamos elegir un subconjunto de estos Nodes de tal manera que la suma de los Nodes seleccionados sea máxima bajo la restricción de que dos Nodes elegidos en el subconjunto no deben estar conectados directamente, es decir, si hemos tomado un Node en nuestra suma, entonces no podemos tomar en consideración a ninguno de sus hijos y viceversa.
Ejemplos:
In the above binary tree, chosen nodes are encircled and are not directly connected, and their sum is maximum possible.
Recomendado: Resuelva primero en «PRÁCTICA» antes de pasar a la solución.
Método 1
Podemos resolver este problema considerando el hecho de que tanto el Node como sus hijos no pueden estar en suma al mismo tiempo, por lo que cuando tomamos un Node en nuestra suma, llamaremos recursivamente a sus nietos o si no Para tomar este Node, llamaremos a todos sus Nodes secundarios y finalmente elegiremos el máximo de ambos resultados.
Se puede ver fácilmente que el enfoque anterior puede llevar a resolver el mismo subproblema muchas veces, por ejemplo, en el diagrama anterior, el Node 1 llama a los Nodes 4 y 5 cuando se elige su valor y el Node 3 también los llama cuando no se elige su valor, por lo que estos Nodes se procesan más de una vez. Podemos dejar de resolver estos Nodes más de una vez memorizando el resultado en todos los Nodes.
En el siguiente código, se utiliza un mapa para memorizar el resultado, que almacena el desarrollo del subárbol completo enraizado en un Node del mapa, de modo que si se vuelve a llamar, el valor no se vuelve a calcular, sino que se almacena el valor del mapa. devuelto directamente.
Por favor, consulte el siguiente código para una mejor comprensión.
C++
// C++ program to find maximum sum from a subset of
// nodes of binary tree
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node structure */
struct node
{
int data;
struct node *left, *right;
};
/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Declaration of methods
int sumOfGrandChildren(node* node);
int getMaxSum(node* node);
int getMaxSumUtil(node* node, map<struct node*, int>& mp);
// method returns maximum sum possible from subtrees rooted
// at grandChildrens of node 'node'
int sumOfGrandChildren(node* node, map<struct node*, int>& mp)
{
int sum = 0;
// call for children of left child only if it is not NULL
if (node->left)
sum += getMaxSumUtil(node->left->left, mp) +
getMaxSumUtil(node->left->right, mp);
// call for children of right child only if it is not NULL
if (node->right)
sum += getMaxSumUtil(node->right->left, mp) +
getMaxSumUtil(node->right->right, mp);
return sum;
}
// Utility method to return maximum sum rooted at node 'node'
int getMaxSumUtil(node* node, map<struct node*, int>& mp)
{
if (node == NULL)
return 0;
// If node is already processed then return calculated
// value from map
if (mp.find(node) != mp.end())
return mp[node];
// take current node value and call for all grand children
int incl = node->data + sumOfGrandChildren(node, mp);
// don't take current node value and call for all children
int excl = getMaxSumUtil(node->left, mp) +
getMaxSumUtil(node->right, mp);
// choose maximum from both above calls and store that in map
mp[node] = max(incl, excl);
return mp[node];
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
int getMaxSum(node* node)
{
if (node == NULL)
return 0;
map<struct node*, int> mp;
return getMaxSumUtil(node, mp);
}
// Driver code to test above methods
int main()
{
node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->left->left = newNode(1);
cout << getMaxSum(root) << endl;
return 0;
}
Java
// Java program to find maximum sum from a subset of
// nodes of binary tree
import java.util.HashMap;
public class FindSumOfNotAdjacentNodes {
// method returns maximum sum possible from subtrees rooted
// at grandChildrens of node 'node'
public static int sumOfGrandChildren(Node node, HashMap<Node,Integer> mp)
{
int sum = 0;
// call for children of left child only if it is not NULL
if (node.left!=null)
sum += getMaxSumUtil(node.left.left, mp) +
getMaxSumUtil(node.left.right, mp);
// call for children of right child only if it is not NULL
if (node.right!=null)
sum += getMaxSumUtil(node.right.left, mp) +
getMaxSumUtil(node.right.right, mp);
return sum;
}
// Utility method to return maximum sum rooted at node 'node'
public static int getMaxSumUtil(Node node, HashMap<Node,Integer> mp)
{
if (node == null)
return 0;
// If node is already processed then return calculated
// value from map
if(mp.containsKey(node))
return mp.get(node);
// take current node value and call for all grand children
int incl = node.data + sumOfGrandChildren(node, mp);
// don't take current node value and call for all children
int excl = getMaxSumUtil(node.left, mp) +
getMaxSumUtil(node.right, mp);
// choose maximum from both above calls and store that in map
mp.put(node,Math.max(incl, excl));
return mp.get(node);
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
public static int getMaxSum(Node node)
{
if (node == null)
return 0;
HashMap<Node,Integer> mp=new HashMap<>();
return getMaxSumUtil(node, mp);
}
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.right = new Node(5);
root.left.left = new Node(1);
System.out.print(getMaxSum(root));
}
}
/* A binary tree node structure */
class Node
{
int data;
Node left, right;
Node(int data)
{
this.data=data;
left=right=null;
}
};
//This code is contributed by Gaurav Tiwari
Python3
# Python3 program to find # maximum sum from a subset # of nodes of binary tree # A binary tree node structure class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Utility function to create # a new Binary Tree node def newNode(data): temp = Node(data) return temp; # method returns maximum sum # possible from subtrees rooted # at grandChildrens of node 'node' def sumOfGrandChildren(node, mp): sum = 0; # call for children of left # child only if it is not NULL if (node.left): sum += (getMaxSumUtil(node.left.left, mp) + getMaxSumUtil(node.left.right, mp)); # call for children of right # child only if it is not NULL if (node.right): sum += (getMaxSumUtil(node.right.left, mp) + getMaxSumUtil(node.right.right, mp)); return sum; # Utility method to return # maximum sum rooted at node # 'node' def getMaxSumUtil(node, mp): if (node == None): return 0; # If node is already processed # then return calculated # value from map if node in mp: return mp[node]; # take current node value # and call for all grand children incl = (node.data + sumOfGrandChildren(node, mp)); # don't take current node # value and call for all children excl = (getMaxSumUtil(node.left, mp) + getMaxSumUtil(node.right, mp)); # choose maximum from both # above calls and store that # in map mp[node] = max(incl, excl); return mp[node]; # Returns maximum sum from # subset of nodes of binary # tree under given constraints def getMaxSum(node): if (node == None): return 0; mp = dict() return getMaxSumUtil(node, mp); # Driver code if __name__=="__main__": root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(5); root.left.left = newNode(1); print(getMaxSum(root)) # This code is contributed by Rutvik_56
C#
// C# program to find maximum sum from a subset of
// nodes of binary tree
using System;
using System.Collections.Generic;
public class FindSumOfNotAdjacentNodes
{
// method returns maximum sum
// possible from subtrees rooted
// at grandChildrens of node 'node'
public static int sumOfGrandChildren(Node node,
Dictionary<Node,int> mp)
{
int sum = 0;
// call for children of left
// child only if it is not NULL
if (node.left != null)
sum += getMaxSumUtil(node.left.left, mp) +
getMaxSumUtil(node.left.right, mp);
// call for children of right
// child only if it is not NULL
if (node.right != null)
sum += getMaxSumUtil(node.right.left, mp) +
getMaxSumUtil(node.right.right, mp);
return sum;
}
// Utility method to return maximum
// sum rooted at node 'node'
public static int getMaxSumUtil(Node node,
Dictionary<Node,int> mp)
{
if (node == null)
return 0;
// If node is already processed then
// return calculated value from map
if(mp.ContainsKey(node))
return mp[node];
// take current node value and
// call for all grand children
int incl = node.data + sumOfGrandChildren(node, mp);
// don't take current node value and
// call for all children
int excl = getMaxSumUtil(node.left, mp) +
getMaxSumUtil(node.right, mp);
// choose maximum from both above
// calls and store that in map
mp.Add(node,Math.Max(incl, excl));
return mp[node];
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
public static int getMaxSum(Node node)
{
if (node == null)
return 0;
Dictionary<Node,int> mp=new Dictionary<Node,int>();
return getMaxSumUtil(node, mp);
}
// Driver code
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.right = new Node(5);
root.left.left = new Node(1);
Console.Write(getMaxSum(root));
}
}
/* A binary tree node structure */
public class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data=data;
left=right=null;
}
};
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find maximum
// sum from a subset of nodes of binary tree
class Node
{
constructor(data)
{
this.left = null;
this.right = null;
this.data = data;
}
}
// Method returns maximum sum possible
// from subtrees rooted at grandChildrens
// of node 'node'
function sumOfGrandChildren(node, mp)
{
let sum = 0;
// Call for children of left child
// only if it is not NULL
if (node.left!=null)
sum += getMaxSumUtil(node.left.left, mp) +
getMaxSumUtil(node.left.right, mp);
// Call for children of right child
// only if it is not NULL
if (node.right!=null)
sum += getMaxSumUtil(node.right.left, mp) +
getMaxSumUtil(node.right.right, mp);
return sum;
}
// Utility method to return maximum
// sum rooted at node 'node'
function getMaxSumUtil(node, mp)
{
if (node == null)
return 0;
// If node is already processed then return
// calculated value from map
if (mp.has(node))
return mp.get(node);
// Take current node value and call for
// all grand children
let incl = node.data + sumOfGrandChildren(node, mp);
// Don't take current node value and call
// for all children
let excl = getMaxSumUtil(node.left, mp) +
getMaxSumUtil(node.right, mp);
// Choose maximum from both above
// calls and store that in map
mp.set(node,Math.max(incl, excl));
return mp.get(node);
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
function getMaxSum(node)
{
if (node == null)
return 0;
let mp = new Map();
return getMaxSumUtil(node, mp);
}
// 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.right = new Node(5);
root.left.left = new Node(1);
document.write(getMaxSum(root));
// This code is contributed by divyeshrabadiya07
</script>
Producción
11
Complejidad temporal: O(n)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Utkarsh Trivedi.
Método 2 (Usando par)
Devuelva un par para cada Node en el árbol binario de modo que el primero del par indique la suma máxima cuando se incluyen los datos de un Node y el segundo indica la suma máxima cuando no se incluyen los datos de un Node en particular .
C++
// C++ program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node* left, *right;
Node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
pair<int, int> maxSumHelper(Node *root)
{
if (root==NULL)
{
pair<int, int> sum(0, 0);
return sum;
}
pair<int, int> sum1 = maxSumHelper(root->left);
pair<int, int> sum2 = maxSumHelper(root->right);
pair<int, int> sum;
// This node is included (Left and right children
// are not included)
sum.first = sum1.second + sum2.second + root->data;
// This node is excluded (Either left or right
// child is included)
sum.second = max(sum1.first, sum1.second) +
max(sum2.first, sum2.second);
return sum;
}
int maxSum(Node *root)
{
pair<int, int> res = maxSumHelper(root);
return max(res.first, res.second);
}
// Driver code
int main()
{
Node *root= new Node(10);
root->left= new Node(1);
root->left->left= new Node(2);
root->left->left->left= new Node(1);
root->left->right= new Node(3);
root->left->right->left= new Node(4);
root->left->right->right= new Node(5);
cout << maxSum(root);
return 0;
}
Java
// Java program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
public class FindSumOfNotAdjacentNodes {
public static Pair maxSumHelper(Node root)
{
if (root==null)
{
Pair sum=new Pair(0, 0);
return sum;
}
Pair sum1 = maxSumHelper(root.left);
Pair sum2 = maxSumHelper(root.right);
Pair sum=new Pair(0,0);
// This node is included (Left and right children
// are not included)
sum.first = sum1.second + sum2.second + root.data;
// This node is excluded (Either left or right
// child is included)
sum.second = Math.max(sum1.first, sum1.second) +
Math.max(sum2.first, sum2.second);
return sum;
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
public static int maxSum(Node root)
{
Pair res=maxSumHelper(root);
return Math.max(res.first, res.second);
}
public static void main(String args[]) {
Node root= new Node(10);
root.left= new Node(1);
root.left.left= new Node(2);
root.left.left.left= new Node(1);
root.left.right= new Node(3);
root.left.right.left= new Node(4);
root.left.right.right= new Node(5);
System.out.print(maxSum(root));
}
}
/* A binary tree node structure */
class Node
{
int data;
Node left, right;
Node(int data)
{
this.data=data;
left=right=null;
}
};
/* Pair class */
class Pair
{
int first,second;
Pair(int first,int second)
{
this.first=first;
this.second=second;
}
}
//This code is contributed by Gaurav Tiwari
Python3
# Python3 program to find maximum sum in Binary # Tree such that no two nodes are adjacent. # Binary Tree Node """ utility that allocates a newNode with the given key """ class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None def maxSumHelper(root) : if (root == None): sum = [0, 0] return sum sum1 = maxSumHelper(root.left) sum2 = maxSumHelper(root.right) sum = [0, 0] # This node is included (Left and right # children are not included) sum[0] = sum1[1] + sum2[1] + root.data # This node is excluded (Either left or # right child is included) sum[1] = (max(sum1[0], sum1[1]) + max(sum2[0], sum2[1])) return sum def maxSum(root) : res = maxSumHelper(root) return max(res[0], res[1]) # Driver Code if __name__ == '__main__': root = newNode(10) root.left = newNode(1) root.left.left = newNode(2) root.left.left.left = newNode(1) root.left.right = newNode(3) root.left.right.left = newNode(4) root.left.right.right = newNode(5) print(maxSum(root)) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
using System;
public class FindSumOfNotAdjacentNodes
{
public static Pair maxSumHelper(Node root)
{
Pair sum;
if (root == null)
{
sum=new Pair(0, 0);
return sum;
}
Pair sum1 = maxSumHelper(root.left);
Pair sum2 = maxSumHelper(root.right);
Pair sum3 = new Pair(0,0);
// This node is included (Left and
// right children are not included)
sum3.first = sum1.second + sum2.second + root.data;
// This node is excluded (Either left
// or right child is included)
sum3.second = Math.Max(sum1.first, sum1.second) +
Math.Max(sum2.first, sum2.second);
return sum3;
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
public static int maxSum(Node root)
{
Pair res=maxSumHelper(root);
return Math.Max(res.first, res.second);
}
// Driver code
public static void Main()
{
Node root = new Node(10);
root.left = new Node(1);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
root.left.right = new Node(3);
root.left.right.left = new Node(4);
root.left.right.right = new Node(5);
Console.Write(maxSum(root));
}
}
/* A binary tree node structure */
public class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
};
/* Pair class */
public class Pair
{
public int first,second;
public Pair(int first,int second)
{
this.first = first;
this.second = second;
}
}
/* This code is contributed PrinciRaj1992 */
Javascript
<script>
// JavaScript program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
/* A binary tree node structure */
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
/* Pair class */
class Pair
{
constructor(first, second)
{
this.first = first;
this.second = second;
}
}
function maxSumHelper(root)
{
var sum;
if (root == null)
{
sum=new Pair(0, 0);
return sum;
}
var sum1 = maxSumHelper(root.left);
var sum2 = maxSumHelper(root.right);
var sum3 = new Pair(0,0);
// This node is included (Left and
// right children are not included)
sum3.first = sum1.second + sum2.second + root.data;
// This node is excluded (Either left
// or right child is included)
sum3.second = Math.max(sum1.first, sum1.second) +
Math.max(sum2.first, sum2.second);
return sum3;
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
function maxSum(root)
{
var res=maxSumHelper(root);
return Math.max(res.first, res.second);
}
// Driver code
var root = new Node(10);
root.left = new Node(1);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
root.left.right = new Node(3);
root.left.right.left = new Node(4);
root.left.right.right = new Node(5);
document.write(maxSum(root));
</script>
Producción
21
Complejidad del tiempo : O(n)
Espacio auxiliar: O(n)
Gracias a Surbhi Rastogi por sugerir este método.
Método 3 ( usando programación dinámica )
Almacene la suma máxima incluyendo un Node o excluyéndolo en una array de dp o en un mapa desordenado. Llama recursivamente a nietos de Nodes si el Node está incluido o llama a vecinos si el Node está excluido.
C++
// C++ program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// declare map /dp array as global
unordered_map<Node*, int> umap;
int maxSum(Node* root)
{
// base case
if (!root)
return 0;
// if the max sum from the node is already in
// map,return the value
if (umap[root])
return umap[root];
// if the current node(root) is included in result
// then find maximum sum
int inc = root->data;
// if left of node exists, add their grandchildren
if (root->left) {
inc += maxSum(root->left->left)
+ maxSum(root->left->right);
}
// if right of node exist,add their grandchildren
if (root->right) {
inc += maxSum(root->right->left)
+ maxSum(root->right->right);
}
// if the current node(root) is excluded, find the
// maximum sum
int ex = maxSum(root->left) + maxSum(root->right);
// store the maximum of including & excluding the node
// in map
umap[root] = max(inc, ex);
return max(inc, ex);
}
// Driver code
int main()
{
Node* root = new Node(10);
root->left = new Node(1);
root->left->left = new Node(2);
root->left->left->left = new Node(1);
root->left->right = new Node(3);
root->left->right->left = new Node(4);
root->left->right->right = new Node(5);
cout << maxSum(root);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
// Java program for the above approach
class GFG {
// Java program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
// declare map /dp array as global
static HashMap<Node,Integer> umap = new HashMap<>();
static int maxSum(Node root)
{
// base case
if (root == null)
return 0;
// if the max sum from the node is already in
// map,return the value
if (umap.containsKey(root))
return umap.get(root);
// if the current node(root) is included in result
// then find maximum sum
int inc = root.data;
// if left of node exists, add their grandchildren
if (root.left != null) {
inc += maxSum(root.left.left)
+ maxSum(root.left.right);
}
// if right of node exist,add their grandchildren
if (root.right != null) {
inc += maxSum(root.right.left)
+ maxSum(root.right.right);
}
// if the current node(root) is excluded, find the
// maximum sum
int ex = maxSum(root.left) + maxSum(root.right);
// store the maximum of including & excluding the node
// in map
umap.put(root, Math.max(inc, ex));
return Math.max(inc, ex);
}
public static void main(String args[])
{
Node root = new Node(10);
root.left = new Node(1);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
root.left.right = new Node(3);
root.left.right.left = new Node(4);
root.left.right.right = new Node(5);
System.out.println(maxSum(root));
}
}
class Node {
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
};
// This code is contributed by code_hunt.
Python3
# Python program to find maximum sum in Binary Tree
# such that no two nodes are adjacent.
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
# declare map /dp array as global
umap = {}
def maxSum(root):
global umap
# base case
if (root == None):
return 0
# if the max sum from the node is already in
# map,return the value
if (root in umap):
return umap[root]
# if the current node(root) is included in result
# then find maximum sum
inc = root.data
# if left of node exists, add their grandchildren
if (root.left):
inc += maxSum(root.left.left) + maxSum(root.left.right)
# if right of node exist,add their grandchildren
if (root.right):
inc += maxSum(root.right.left) + maxSum(root.right.right)
# if the current node(root) is excluded, find the
# maximum sum
ex = maxSum(root.left) + maxSum(root.right)
# store the maximum of including & excluding the node
# in map
umap[root]=max(inc, ex)
return max(inc, ex)
# Driver code
root = Node(10)
root.left = Node(1)
root.left.left = Node(2)
root.left.left.left = Node(1)
root.left.right = Node(3)
root.left.right.left = Node(4)
root.left.right.right = Node(5)
print(maxSum(root))
# This code is contributed by shinjanpatra
C#
// C# program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
using System;
using System.Collections.Generic;
/* A binary tree node structure */
public class Node {
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
};
class GFG {
// declare map /dp array as global
static Dictionary<Node, int> umap
= new Dictionary<Node, int>();
static int maxSum(Node root)
{
// base case
if (root == null)
return 0;
// if the max sum from the node is already in
// map,return the value
if (umap.ContainsKey(root))
return umap[root];
// if the current node(root) is included in result
// then find maximum sum
int inc = root.data;
// if left of node exists, add their grandchildren
if (root.left != null) {
inc += maxSum(root.left.left)
+ maxSum(root.left.right);
}
// if right of node exist,add their grandchildren
if (root.right != null) {
inc += maxSum(root.right.left)
+ maxSum(root.right.right);
}
// if the current node(root) is excluded, find the
// maximum sum
int ex = maxSum(root.left) + maxSum(root.right);
// store the maximum of including & excluding the
// node in map
umap.Add(root, Math.Max(inc, ex));
return Math.Max(inc, ex);
}
// Driver code
public static void Main(String[] args)
{
Node root = new Node(10);
root.left = new Node(1);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
root.left.right = new Node(3);
root.left.right.left = new Node(4);
root.left.right.right = new Node(5);
Console.Write(maxSum(root));
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Javascript
<script>
// JavaScript program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
class Node {
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// declare map /dp array as global
let umap = new Map();
function maxSum(root)
{
// base case
if (!root)
return 0;
// if the max sum from the node is already in
// map,return the value
if (umap.has(root))
return umap.get(root);
// if the current node(root) is included in result
// then find maximum sum
let inc = root.data;
// if left of node exists, add their grandchildren
if (root.left) {
inc += maxSum(root.left.left)
+ maxSum(root.left.right);
}
// if right of node exist,add their grandchildren
if (root.right) {
inc += maxSum(root.right.left)
+ maxSum(root.right.right);
}
// if the current node(root) is excluded, find the
// maximum sum
let ex = maxSum(root.left) + maxSum(root.right);
// store the maximum of including & excluding the node
// in map
umap.set(root,Math.max(inc, ex));
return Math.max(inc, ex);
}
// Driver code
let root = new Node(10);
root.left = new Node(1);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
root.left.right = new Node(3);
root.left.right.left = new Node(4);
root.left.right.right = new Node(5);
document.write(maxSum(root));
// This code is contributed by shinjanpatra
</script>
Producción
21
Complejidad temporal: O(n) Espacio
auxiliar : O(n)
Este artículo es una contribución de Harsh.< https://auth.geeksforgeeks.org/user/harshchandekar10/profile >
Método 4 (recorrido de árbol simple)
Para cada Node, encontramos lo siguiente:
- Suma máxima de Nodes no adyacentes incluido el Node.
- Suma máxima de Nodes no adyacentes excluyendo el Node.
Ahora, devolvemos ambos valores en la llamada recursiva. El Node padre del Node previamente calculado obtiene la suma máxima (incluyendo y excluyendo) el Node hijo. En consecuencia, el padre ahora calcula la suma máxima (incluyendo y excluyendo) y devuelve. Este proceso continúa hasta el Node raíz. Finalmente, devolvemos el máximo (la suma incluye la raíz, la suma excluye la raíz).
Complejidad de tiempo: O(n)
Complejidad espacial: O(1)
C++
// C++ Code for above approach
class Node {
public:
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
pair<int, int> max_sum(Node* root)
{
if (!root)
return {0, 0};
auto left = max_sum(root->left);
auto right = max_sum(root->right);
int no_root_l = left.first, root_l = left.second;
int no_root_r = right.first, root_r = right.second;
int root_sum_max = max(max(root->data, root->data+no_root_l),
max(root->data+no_root_r, root->data+no_root_r+no_root_l));
int no_root_sum_max = max(max(root_l, root_r), max(max(root_l + root_r, no_root_l+no_root_r), max(root_l + no_root_r, root_r + no_root_l)));
return {no_root_sum_max, root_sum_max};
}
int getMaxSum(Node* root){
pair<int, int> ans = max_sum(root);
return max(ans.first, ans.second);
}
// This code is contributed by Tapesh(tapeshdua420)
Python3
class Node: def __init__(self, val): self.data = val self.left = None self.right = None class Solution: def max_sum(self, root): if not root: return 0, 0 no_root_l, root_l = self.max_sum(root.left) no_root_r, root_r = self.max_sum(root.right) root_sum_max = max(root.data, root.data+no_root_l, root.data+no_root_r, root.data+no_root_r+no_root_l) no_root_sum_max = max(root_l, root_r, root_l + root_r, no_root_l+no_root_r, root_l + no_root_r, root_r + no_root_l) return no_root_sum_max, root_sum_max def getMaxSum(self, root): return max(self.max_sum(root))
Javascript
<script>
// JavaScript code to implement the approach
class Node{
constructor(val){
this.data = val
this.left = null
this.right = null
}
}
class Solution{
max_sum(root){
if(root == null)
return 0, 0
let no_root_l, root_l = this.max_sum(root.left)
let no_root_r, root_r = this.max_sum(root.right)
let root_sum_max = Math.max(root.data, root.data+no_root_l,
root.data+no_root_r, root.data+no_root_r+no_root_l)
let no_root_sum_max = Math.max(root_l, root_r, root_l + root_r, no_root_l+no_root_r,
root_l + no_root_r, root_r + no_root_l)
return no_root_sum_max, root_sum_max
}
getMaxSum(root){
return Math.max(this.max_sum(root))
}
}
// This code is contributed by shinjanpatra
</script>
Este método es aportado por Thatikonda Aditya.
Método 5 (usando la memorización)
Enfoque: para cada Node, podemos elegirlo o dejarlo y pasar esta información a los niños. Dado que estamos pasando esta información de la selección del padre o no, no tenemos que preocuparnos por los nietos del Node.
Entonces, para cada Node, hacemos lo siguiente:
- Si se selecciona el padre, no seleccionamos el Node actual y pasamos a los hijos.
- si el padre no está seleccionado, seleccionaremos o no seleccionaremos este Node; en cualquier caso, pasamos esa información a los niños.
A continuación se muestra la implementación del método anterior:
C++
// C++ program to find maximum sum from a subset of
// non-adjacent nodes of binary tree
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node structure */
struct Node
{
int data;
struct Node *left, *right;
};
/* Utility function to create a new Binary Tree node */
struct Node *newNode(int data)
{
struct Node *temp = new struct Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Delaration of the vector to store the answer
vector<vector<int>> dp;
// Variables and function to index the given Binary tree
// This indexing will be used in dp
int cnt = 0;
Node *temp;
Node *giveIndex(Node *root)
{
if (root == NULL)
return NULL;
// give the index to the current node and increment the index for next nodes.
Node *newNode1 = newNode(cnt++);
// Recursively calling right and left subtree
newNode1->left = giveIndex(root->left);
newNode1->right = giveIndex(root->right);
return newNode1;
}
// Memoization function to store the answer
int solve(Node *root, int b, Node *temp)
{
if (root == NULL)
return 0;
// If the answer is already calculated return that answer
if (dp[temp->data][b] != -1)
return dp[temp->data][b];
// Variable to store the answer for the current node.
int res;
// if the parent is not selected then we can either select ot not select this node.
if (b == 0)
res = max(root->data + solve(root->right, 1, temp->right) + solve(root->left, 1, temp->left), solve(root->right, 0, temp->right) + solve(root->left, 0, temp->left));
// If parent is selected then we can't select this node.
else
res = solve(root->right, 0, temp->right) + solve(root->left, 0, temp->left);
// return the annswer
return dp[temp->data][b] = res;
}
int getMaxSum(Node *root)
{
// Initialization of the dp
dp = vector<vector<int>>(100, vector<int>(2, -1));
// Calling the indexing function
temp = giveIndex(root);
// calling the solve function for root with parent not selected
int res = solve(root, 0, temp);
return res;
}
// Driver code to test above methods
int main()
{
// TEST 1
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->left->left = newNode(1);
cout << getMaxSum(root) << endl;
// TEST 2
Node *root2 = newNode(10);
root2->left = newNode(1);
root2->left->left = newNode(2);
root2->left->left->left = newNode(1);
root2->left->right = newNode(3);
root2->left->right->left = newNode(4);
root2->left->right->right = newNode(5);
cout << getMaxSum(root2);
return 0;
}
//Code contributed by Anirudh Singh.
Java
// Java program to find maximum sum from a subset of
// non-adjacent nodes of binary tree
import java.util.HashMap;
/* A binary tree node structure */
class Node {
int data;
Node left, right;
Node(int data)
{
this.data = data;
left = right = null;
}
};
class gfg {
// Delaration of the vector to store the answer
static int[][] dp;
// Variables and function to index the given Binary tree
// This indexing will be used in dp
static int cnt = 0;
static Node temp;
static Node giveIndex(Node root)
{
if (root == null)
return null;
// give the index to the current node and increment
// the index for next nodes.
Node newNode1 = new Node(cnt++);
// Recursively calling right and left subtree
newNode1.left = giveIndex(root.left);
newNode1.right = giveIndex(root.right);
return newNode1;
}
// Memoization function to store the answer
static int solve(Node root, int b, Node temp)
{
if (root == null)
return 0;
// If the answer is already calculated return that
// answer
if (dp[temp.data][b] != -1)
return dp[temp.data][b];
// Variable to store the answer for the current
// node.
int res;
// if the parent is not selected then we can either
// select ot not select this node.
if (b == 0)
res = Math.max(root.data + solve(root.right, 1, temp.right)
+ solve(root.left, 1, temp.left),
solve(root.right, 0, temp.right)
+ solve(root.left, 0, temp.left));
// If parent is selected then we can't select this
// node.
else
res = solve(root.right, 0, temp.right)
+ solve(root.left, 0, temp.left);
// return the annswer
return dp[temp.data][b] = res;
}
static int getMaxSum(Node root)
{
// Initialization of the dp
dp = new int[100][2];
for(int i=0;i<100;i++)
{
dp[i][0] = -1;
dp[i][1] = -1;
}
// Calling the indexing function
temp = giveIndex(root);
// calling the solve function for root with parent
// not selected
int res = solve(root, 0, temp);
return res;
}
public static void main(String args[])
{
// TEST 1
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(5);
root.left.left = new Node(1);
System.out.println(getMaxSum(root));
// TEST 2
Node root2 = new Node(10);
root2.left = new Node(1);
root2.left.left = new Node(2);
root2.left.left.left = new Node(1);
root2.left.right = new Node(3);
root2.left.right.left = new Node(4);
root2.left.right.right = new Node(5);
System.out.print(getMaxSum(root2));
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python3 program to find maximum sum from a subset of # non-adjacent nodes of binary tree # A binary tree node structure class newNode: def __init__(self, data): self.data = data self.left = None self.right = None dp = [[]] # Variables and function to index the given Binary tree # This indexing will be used in dp cnt = 0 temp = newNode(0) def giveIndex(root): if (root == None): return None # give the index to the current node and increment the index for next nodes. global cnt cnt += 1 newNode1 = newNode(cnt) # Recursively calling right and left subtree newNode1.left = giveIndex(root.left) newNode1.right = giveIndex(root.right) return newNode1 # Memoization function to store the answer def solve(root, b, temp): if (root == None): return 0 # If the answer is already calculated return that answer if (dp[temp.data][b] != -1): return dp[temp.data][b] # Variable to store the answer for the current node. res = 0 # if the parent is not selected then we can either select ot not select this node. if (b == 0): res = max(root.data + solve(root.right, 1, temp.right) + solve(root.left, 1, temp.left), solve(root.right, 0, temp.right) + solve(root.left, 0, temp.left)) # If parent is selected then we can't select this node. else: res = solve(root.right, 0, temp.right) + solve(root.left, 0, temp.left) # return the annswer dp[temp.data][b] = res return res def getMaxSum(root): # Initialization of the dp global dp dp = [[-1 for x in range(2)] for x in range(100)] # Calling the indexing function temp = giveIndex(root) # calling the solve function for root with parent not selected res = solve(root, 0, temp) return res # Driver code if __name__=="__main__": # TEST 1 root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.right.left = newNode(4) root.right.right = newNode(5) root.left.left = newNode(1) print(getMaxSum(root)) # TEST 2 root2 = newNode(10) root2.left = newNode(1) root2.left.left = newNode(2) root2.left.left.left = newNode(1) root2.left.right = newNode(3) root2.left.right.left = newNode(4) root2.left.right.right = newNode(5) print(getMaxSum(root2)) # This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to find maximum sum from a subset of
// non-adjacent nodes of binary tree
using System;
using System.Collections.Generic;
/* A binary tree node structure */
public class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data=data;
left=right=null;
}
};
class gfg
{
// Delaration of the vector to store the answer
static int[,] dp;
// Variables and function to index the given Binary tree
// This indexing will be used in dp
static int cnt = 0;
static Node temp;
static Node giveIndex(Node root)
{
if (root == null)
return null;
// give the index to the current node and increment
// the index for next nodes.
Node newNode1 = new Node(cnt++);
// Recursively calling right and left subtree
newNode1.left = giveIndex(root.left);
newNode1.right = giveIndex(root.right);
return newNode1;
}
// Memoization function to store the answer
static int solve(Node root, int b, Node temp)
{
if (root == null)
return 0;
// If the answer is already calculated return that
// answer
if (dp[temp.data,b] != -1)
return dp[temp.data,b];
// Variable to store the answer for the current
// node.
int res;
// if the parent is not selected then we can either
// select ot not select this node.
if (b == 0)
res = Math.Max(root.data + solve(root.right, 1, temp.right)
+ solve(root.left, 1, temp.left),
solve(root.right, 0, temp.right)
+ solve(root.left, 0, temp.left));
// If parent is selected then we can't select this
// node.
else
res = solve(root.right, 0, temp.right)
+ solve(root.left, 0, temp.left);
// return the annswer
return dp[temp.data,b] = res;
}
static int getMaxSum(Node root)
{
// Initialization of the dp
dp = new int[100,2];
for(int i=0;i<100;i++)
{
dp[i,0] = -1;
dp[i,1] = -1;
}
// Calling the indexing function
temp = giveIndex(root);
// calling the solve function for root with parent
// not selected
int res = solve(root, 0, temp);
return res;
}
// Driver code
public static void Main(String []args)
{
// TEST 1
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(5);
root.left.left = new Node(1);
Console.WriteLine(getMaxSum(root));
// TEST 2
Node root2 = new Node(10);
root2.left = new Node(1);
root2.left.left = new Node(2);
root2.left.left.left = new Node(1);
root2.left.right = new Node(3);
root2.left.right.left = new Node(4);
root2.left.right.right = new Node(5);
Console.Write(getMaxSum(root2));
}
}
// This code has been contributed by Abhijeet Kumar(abhijeet19403)
Producción
11 21
Complejidad de tiempo: O(N)
Complejidad espacial: O(N)
Este método y su implementación son aportados por Anirudh Singh.
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 review-team@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