Dado un árbol binario que contiene n Nodes. El problema es obtener la suma de todos los Nodes hoja que se encuentran en el nivel mínimo del árbol binario.
Ejemplos:
C++
// C++ implementation to find the sum of
// leaf nodes at minimum level
#include <bits/stdc++.h>
using namespace std;
// structure of a node of binary tree
struct Node {
int data;
Node *left, *right;
};
// function to get a new node
Node* getNode(int data)
{
// allocate space
Node* newNode = (Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// function to find the sum of
// leaf nodes at minimum level
int sumOfLeafNodesAtMinLevel(Node* root)
{
// if tree is empty
if (!root)
return 0;
// if there is only one node
if (!root->left && !root->right)
return root->data;
// queue used for level order traversal
queue<Node*> q;
int sum = 0;
bool f = 0;
// push root node in the queue 'q'
q.push(root);
while (f == 0) {
// count number of nodes in the
// current level
int nc = q.size();
// traverse the current level nodes
while (nc--) {
// get front element from 'q'
Node* top = q.front();
q.pop();
// if it is a leaf node
if (!top->left && !top->right) {
// accumulate data to 'sum'
sum += top->data;
// set flag 'f' to 1, to signify
// minimum level for leaf nodes
// has been encountered
f = 1;
}
else {
// if top's left and right child
// exists, then push them to 'q'
if (top->left)
q.push(top->left);
if (top->right)
q.push(top->right);
}
}
}
// required sum
return sum;
}
// Driver program to test above
int main()
{
// binary tree creation
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->left->right->left = getNode(8);
root->right->left->right = getNode(9);
cout << "Sum = "
<< sumOfLeafNodesAtMinLevel(root);
return 0;
}
Java
// Java implementation to find the sum of
// leaf nodes at minimum level
import java.util.*;
class GFG
{
// structure of a node of binary tree
static class Node
{
int data;
Node left, right;
};
// function to get a new node
static Node getNode(int data)
{
// allocate space
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// function to find the sum of
// leaf nodes at minimum level
static int sumOfLeafNodesAtMinLevel(Node root)
{
// if tree is empty
if (root == null)
return 0;
// if there is only one node
if (root.left == null &&
root.right == null)
return root.data;
// queue used for level order traversal
Queue<Node> q = new LinkedList<>();
int sum = 0;
boolean f = false;
// push root node in the queue 'q'
q.add(root);
while (f == false)
{
// count number of nodes in the
// current level
int nc = q.size();
// traverse the current level nodes
while (nc-- >0)
{
// get front element from 'q'
Node top = q.peek();
q.remove();
// if it is a leaf node
if (top.left == null &&
top.right == null)
{
// accumulate data to 'sum'
sum += top.data;
// set flag 'f' to 1, to signify
// minimum level for leaf nodes
// has been encountered
f = true;
}
else
{
// if top's left and right child
// exists, then push them to 'q'
if (top.left != null)
q.add(top.left);
if (top.right != null)
q.add(top.right);
}
}
}
// required sum
return sum;
}
// Driver Code
public static void main(String[] args)
{
// binary tree creation
Node root = getNode(1);
root.left = getNode(2);
root.right = getNode(3);
root.left.left = getNode(4);
root.left.right = getNode(5);
root.right.left = getNode(6);
root.right.right = getNode(7);
root.left.right.left = getNode(8);
root.right.left.right = getNode(9);
System.out.println("Sum = " +
sumOfLeafNodesAtMinLevel(root));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find the sum
# of leaf node at minimum level
from collections import deque
# Structure of a node in binary tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# function to find the sum of leaf nodes
# at minimum level
def sumOfLeafNodesAtLeafLevel(root):
# if tree is empty
if not root:
return 0
# if there is only root node
if not root.left and not root.right:
return root.data
# Queue used for level order traversal
Queue = deque()
sum = f = 0
# push root node in the queue
Queue.append(root)
while not f:
# count no. of nodes present at current level
nc = len(Queue)
# traverse current level nodes
while nc:
top = Queue.popleft()
# if node is leaf node
if not top.left and not top.right:
sum += top.data
# set flag = 1 to signify that
# we have encountered the minimum level
f = 1
else:
# if top's left or right child exist
# push them to Queue
if top.left:
Queue.append(top.left)
if top.right:
Queue.append(top.right)
nc -= 1
# return the sum
return sum
# Driver code
if __name__ == "__main__":
# binary tree creation
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.right.left.right = Node(9)
print("Sum = ", sumOfLeafNodesAtLeafLevel(root))
# This code is contributed by
# Mayank Chaudhary (chaudhary_19)
C#
// C# implementation to find the sum of
// leaf nodes at minimum level
using System;
using System.Collections.Generic;
class GFG
{
// structure of a node of binary tree
class Node
{
public int data;
public Node left, right;
};
// function to get a new node
static Node getNode(int data)
{
// allocate space
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// function to find the sum of
// leaf nodes at minimum level
static int sumOfLeafNodesAtMinLevel(Node root)
{
// if tree is empty
if (root == null)
return 0;
// if there is only one node
if (root.left == null &&
root.right == null)
return root.data;
// queue used for level order traversal
Queue<Node> q = new Queue<Node>();
int sum = 0;
bool f = false;
// push root node in the queue 'q'
q.Enqueue(root);
while (f == false)
{
// count number of nodes in the
// current level
int nc = q.Count;
// traverse the current level nodes
while (nc-- >0)
{
// get front element from 'q'
Node top = q.Peek();
q.Dequeue();
// if it is a leaf node
if (top.left == null &&
top.right == null)
{
// accumulate data to 'sum'
sum += top.data;
// set flag 'f' to 1, to signify
// minimum level for leaf nodes
// has been encountered
f = true;
}
else
{
// if top's left and right child
// exists, then push them to 'q'
if (top.left != null)
q.Enqueue(top.left);
if (top.right != null)
q.Enqueue(top.right);
}
}
}
// required sum
return sum;
}
// Driver Code
public static void Main(String[] args)
{
// binary tree creation
Node root = getNode(1);
root.left = getNode(2);
root.right = getNode(3);
root.left.left = getNode(4);
root.left.right = getNode(5);
root.right.left = getNode(6);
root.right.right = getNode(7);
root.left.right.left = getNode(8);
root.right.left.right = getNode(9);
Console.WriteLine("Sum = " +
sumOfLeafNodesAtMinLevel(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation to find the sum of
// leaf nodes at minimum level
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// function to get a new node
function getNode(data)
{
// allocate space
let newNode = new Node(data);
return newNode;
}
// function to find the sum of
// leaf nodes at minimum level
function sumOfLeafNodesAtMinLevel(root)
{
// if tree is empty
if (root == null)
return 0;
// if there is only one node
if (root.left == null &&
root.right == null)
return root.data;
// queue used for level order traversal
let q = [];
let sum = 0;
let f = false;
// push root node in the queue 'q'
q.push(root);
while (f == false)
{
// count number of nodes in the
// current level
let nc = q.length;
// traverse the current level nodes
while (nc-- >0)
{
// get front element from 'q'
let top = q[0];
q.shift();
// if it is a leaf node
if (top.left == null &&
top.right == null)
{
// accumulate data to 'sum'
sum += top.data;
// set flag 'f' to 1, to signify
// minimum level for leaf nodes
// has been encountered
f = true;
}
else
{
// if top's left and right child
// exists, then push them to 'q'
if (top.left != null)
q.push(top.left);
if (top.right != null)
q.push(top.right);
}
}
}
// required sum
return sum;
}
// binary tree creation
let root = getNode(1);
root.left = getNode(2);
root.right = getNode(3);
root.left.left = getNode(4);
root.left.right = getNode(5);
root.right.left = getNode(6);
root.right.right = getNode(7);
root.left.right.left = getNode(8);
root.right.left.right = getNode(9);
document.write("Sum = " +
sumOfLeafNodesAtMinLevel(root));
</script>
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
// function to get a new node
Node* getNode(int data)
{
// allocate space
Node* newNode = (Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
map <int, vector <int>> mp;
void solve(Node* root, int level) {
if(root == NULL)
return;
if(root->left == NULL && root->right == NULL)
mp[level].push_back(root->data);
solve(root->left, level+1);
solve(root->right, level+1);
}
int minLeafSum(Node *root)
{
solve(root, 0);
int sum = 0;
for(auto i:mp) {
for(auto j:i.second) {
sum += j;
}
return sum;
}
}
int main() {
// binary tree creation
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
cout << "Sum = "<< minLeafSum(root);
return 0;
}
Java
// Java implementation ofabove approach
import java.util.TreeMap;
import java.util.Vector;
import java.util.Map.Entry;
class GFG {
static class Node {
int data;
Node left, right;
};
// function to get a new node
static Node getNode(int data)
{
// allocate space
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
static TreeMap<Integer, Vector <Integer>> mp = new TreeMap <Integer, Vector <Integer>>();
static void solve(Node root, int level) {
if(root == null)
return;
if(root.left == null && root.right == null)
{
Vector<Integer> get = mp.get(level);
if(get == null)
{
get = new Vector<>();
get.add(root.data);
}
else
get.add(root.data);
mp.put(level, get);
}
solve(root.left, level+1);
solve(root.right, level+1);
}
static int minLeafSum(Node root)
{
solve(root, 0);
int sum = 0;
for (Entry<Integer, Vector<Integer>> i : mp.entrySet())
{
for(Integer j : i.getValue())
{
sum+=j;
}
return sum;
}
return 0;
}
// Driver Code
public static void main(String[] args)
{
// binary tree creation
Node root = getNode(1);
root.left = getNode(2);
root.right = getNode(3);
root.left.left = getNode(4);
root.left.right = getNode(5);
root.right.left = getNode(6);
root.right.right = getNode(7);
System.out.println(
"Sum = " + minLeafSum(root));
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python3 implementation of above approach
# Structure of a node in binary tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
mp = dict()
def solve(root,level):
if(root == None):
return
if root.left == None and root.right == None :
try:
mp[level].append(root.data)
except:
mp[level] = [root.data]
solve(root.left, level+1)
solve(root.right, level+1)
def minLeafSum(root):
solve(root, 0)
sum = 0
for x, i in enumerate(sorted(mp)):
for j in mp[i]:
sum += j
return sum
# Driver code
if __name__ == "__main__":
# binary tree creation
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Sum = ", minLeafSum(root))
# This code is contributed by
# Abhijeet Kumar(abhijeet19403)
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG {
// structure of a node of binary tree
class Node {
public int data;
public Node left, right;
};
// function to get a new node
static Node getNode(int data)
{
// allocate space
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
static SortedDictionary<int, List<int> > mp
= new SortedDictionary<int, List<int> >();
static void solve(Node root, int level)
{
if (root == null)
return;
if (root.left == null && root.right == null) {
List<int> get = new List<int>();
if (mp.ContainsKey(level))
get.AddRange(mp[level]);
if (get == null) {
get = new List<int>();
get.Add(root.data);
}
else
get.Add(root.data);
mp[level] = get;
}
solve(root.left, level + 1);
solve(root.right, level + 1);
}
static int minLeafSum(Node root)
{
solve(root, 0);
int sum = 0;
foreach(KeyValuePair<int, List<int> > i in mp)
{
foreach(int j in i.Value) sum += j;
return sum;
}
return 0;
}
// Driver Code
public static void Main(String[] args)
{
// binary tree creation
Node root = getNode(1);
root.left = getNode(2);
root.right = getNode(3);
root.left.left = getNode(4);
root.left.right = getNode(5);
root.right.left = getNode(6);
root.right.right = getNode(7);
Console.WriteLine("Sum = " + minLeafSum(root));
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA