Dado un árbol binario que tiene Nodes positivos y negativos, la tarea es encontrar la suma máxima de Nodes hoja entre todos los niveles del árbol binario dado.
Ejemplos:
Input:
4
/ \
2 -5
/ \
-1 3
Output: 2
Sum of all leaves at 0th level is 0.
Sum of all leaves at 1st level is -5.
Sum of all leaves at 2nd level is 2.
Hence maximum sum is 2.
Input:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
Output: 13
Enfoque: La idea para resolver el problema anterior es hacer un recorrido del árbol por orden de niveles . Mientras realiza el recorrido, procese los Nodes de diferentes niveles por separado. Para cada nivel que se procese, calcule la suma de los Nodes hoja en el nivel y realice un seguimiento de la suma máxima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct Node {
int data;
struct Node *left, *right;
};
// Function to return the maximum sum of leaf nodes
// at any level in tree using level order traversal
int maxLeafNodesSum(struct Node* root)
{
// Base case
if (root == NULL)
return 0;
// Initialize result
int result = 0;
// Do Level order traversal keeping track
// of the number of nodes at every level
queue<Node*> q;
q.push(root);
while (!q.empty()) {
// Get the size of queue when the level order
// traversal for one level finishes
int count = q.size();
// Iterate for all the nodes in the queue currently
int sum = 0;
while (count--) {
// Dequeue an node from queue
Node* temp = q.front();
q.pop();
// Add leaf node's value to current sum
if (temp->left == NULL && temp->right == NULL)
sum = sum + temp->data;
// Enqueue left and right children of
// dequeued node
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
// Update the maximum sum of leaf nodes value
result = max(sum, result);
}
return result;
}
// Helper function that allocates a new node with the
// given data and NULL left and right pointers
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Driver code
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->right = newNode(8);
root->right->right->left = newNode(6);
root->right->right->right = newNode(7);
cout << maxLeafNodesSum(root) << endl;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// A binary tree node has data,
// pointer to left child and
// a pointer to right child
static class Node
{
int data;
Node left, right;
};
// Function to return the maximum sum
// of leaf nodes at any level in tree
// using level order traversal
static int maxLeafNodesSum(Node root)
{
// Base case
if (root == null)
return 0;
// Initialize result
int result = 0;
// Do Level order traversal keeping track
// of the number of nodes at every level
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty())
{
// Get the size of queue when the level order
// traversal for one level finishes
int count = q.size();
// Iterate for all the nodes
// in the queue currently
int sum = 0;
while (count-- > 0)
{
// Dequeue an node from queue
Node temp = q.peek();
q.remove();
// Add leaf node's value to current sum
if (temp.left == null &&
temp.right == null)
sum = sum + temp.data;
// Enqueue left and right children of
// dequeued node
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
// Update the maximum sum of leaf nodes value
result = Math.max(sum, result);
}
return result;
}
// Helper function that allocates a new node with the
// given data and null left and right pointers
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Driver code
public static void main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.right = newNode(8);
root.right.right.left = newNode(6);
root.right.right.right = newNode(7);
System.out.println(maxLeafNodesSum(root));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # A binary tree node has data, # pointer to left child and # a pointer to right child # Helper function that allocates # a new node with the given data # and None left and right pointers class newNode: def __init__(self, data): self.data = data self.left = None self.right = None # Function to return the maximum sum # of leaf nodes at any level in tree # using level order traversal def maxLeafNodesSum(root): # Base case if (root == None): return 0 # Initialize result result = 0 # Do Level order traversal keeping track # of the number of nodes at every level q = [] q.append(root) while(len(q)): # Get the size of queue when the level order # traversal for one level finishes count = len(q) # Iterate for all the nodes # in the queue currently sum = 0 while (count): # Dequeue an node from queue temp = q[0] q.pop(0) # Add leaf node's value to current sum if (temp.left == None and temp.right == None): sum = sum + temp.data # Enqueue left and right children of # dequeued node if (temp.left != None): q.append(temp.left) if (temp.right != None): q.append(temp.right) count -= 1 # Update the maximum sum # of leaf nodes value result = max(sum, result) return result # Driver code root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.right.right = newNode(8) root.right.right.left = newNode(6) root.right.right.right = newNode(7) print(maxLeafNodesSum(root)) # This code is contributed by SHUBHAMSINGH10
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// A binary tree node has data,
// pointer to left child and
// a pointer to right child
class Node
{
public int data;
public Node left, right;
};
// Function to return the maximum sum
// of leaf nodes at any level in tree
// using level order traversal
static int maxLeafNodesSum(Node root)
{
// Base case
if (root == null)
return 0;
// Initialize result
int result = 0;
// Do Level order traversal keeping track
// of the number of nodes at every level
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count != 0)
{
// Get the size of queue when the level order
// traversal for one level finishes
int count = q.Count;
// Iterate for all the nodes
// in the queue currently
int sum = 0;
while (count-- > 0)
{
// Dequeue an node from queue
Node temp = q.Peek();
q.Dequeue();
// Add leaf node's value to current sum
if (temp.left == null &&
temp.right == null)
sum = sum + temp.data;
// Enqueue left and right children of
// dequeued node
if (temp.left != null)
q.Enqueue(temp.left);
if (temp.right != null)
q.Enqueue(temp.right);
}
// Update the maximum sum of leaf nodes value
result = Math.Max(sum, result);
}
return result;
}
// Helper function that allocates a new node with the
// given data and null left and right pointers
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Driver code
public static void Main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.right = newNode(8);
root.right.right.left = newNode(6);
root.right.right.right = newNode(7);
Console.WriteLine(maxLeafNodesSum(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the approach
// A binary tree node has data,
// pointer to left child and
// a pointer to right child
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to return the maximum sum
// of leaf nodes at any level in tree
// using level order traversal
function maxLeafNodesSum(root)
{
// Base case
if (root == null)
return 0;
// Initialize result
let result = 0;
// Do Level order traversal keeping track
// of the number of nodes at every level
let q = [];
q.push(root);
while (q.length > 0)
{
// Get the size of queue when the level order
// traversal for one level finishes
let count = q.length;
// Iterate for all the nodes
// in the queue currently
let sum = 0;
while (count-- > 0)
{
// Dequeue an node from queue
let temp = q[0];
q.shift();
// Add leaf node's value to current sum
if (temp.left == null &&
temp.right == null)
sum = sum + temp.data;
// Enqueue left and right children of
// dequeued node
if (temp.left != null)
q.push(temp.left);
if (temp.right != null)
q.push(temp.right);
}
// Update the maximum sum of leaf nodes value
result = Math.max(sum, result);
}
return result;
}
// Helper function that allocates a new node with the
// given data and null left and right pointers
function newNode(data)
{
let node = new Node(data);
return (node);
}
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.right = newNode(8);
root.right.right.left = newNode(6);
root.right.right.right = newNode(7);
document.write(maxLeafNodesSum(root));
</script>
Producción:
13
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA