Dado un árbol binario , la tarea es encontrar la suma de los Nodes hoja en cada nivel del árbol dado .
Ejemplos:
Aporte:
Salida:
0
0
6
30
12
Explicación:
Nivel 1: sin Node de hoja, por lo que suma = 0
Nivel 2: sin Node de hoja, por lo que suma = 0
Nivel 3: un Node de hoja: 6, por lo que suma = 6
Nivel 4: tres Nodes de hoja : 9, 10, 11, así que suma = 30
Nivel 5: Node de una hoja: 12, así que suma = 12Aporte:
Salida:
0
0
6
28
Enfoque: El problema dado se puede resolver utilizando el recorrido de orden de nivel . Siga los pasos a continuación para resolver el problema dado:
- Cree una cola qu para almacenar el Node junto con su nivel. Además, cree un mapa para almacenar la suma de cada nivel.
- Realice el recorrido del orden de nivel desde el Node raíz y almacene cada Node con su nivel en la cola, y también verifique el Node actual para el Node hoja . Si es un Node hoja, agregue su valor en el mapa correspondiente a su nivel.
- Después de completar los pasos anteriores, imprima los valores en el mapa como la suma de cada nivel del árbol dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Tree node structure
class Node {
public:
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Function to print the sum of leaf nodes
// at each horizontal level
void printLevelSum(Node* root)
{
if (root == NULL) {
cout << "No nodes present\n";
return;
}
// Map to hold sum at each level
map<int, int> mp;
// Queue to hold tree node with level
queue<pair<Node*, int> > q;
// Root node is at level 1
q.push({ root, 1 });
pair<Node*, int> p;
// Level Order Traversal of tree
while (!q.empty()) {
p = q.front();
q.pop();
// Create a key for each level
// in the map
if (mp.find(p.second) == mp.end()) {
mp[p.second] = 0;
}
// If current node is a leaf node
if (p.first->left == NULL
&& p.first->right == NULL) {
// Adding value in the map
// corresponding to its level
mp[p.second] += p.first->data;
}
if (p.first->left)
q.push({ p.first->left, p.second + 1 });
if (p.first->right)
q.push({ p.first->right, p.second + 1 });
}
// Print the sum at each level
for (auto i : mp) {
cout << i.second << endl;
}
}
// Driver Code
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->right = new Node(8);
root->left->right->right = new Node(9);
root->right->right->left = new Node(10);
root->right->right->right = new Node(11);
root->left->left->right->right = new Node(12);
printLevelSum(root);
return 0;
}
Java
// Java program for the above approach
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.HashMap;
public class Print_Level_Sum_Btree {
/* A tree node structure */
static class Node {
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left = null;
right = null;
}
}
// User defined class Pair to hold
// the node and its level
static class Pair{
Node n;
int i;
Pair(Node n, int i){
this.n = n;
this.i = i;
}
}
// Function to print the sum of leaf nodes
// at each horizontal level
static void printLevelSum(Node root)
{
if (root == null)
{
System.out.println("No nodes present");
return;
}
// hashmap to hold sum at each level
HashMap<Integer, Integer> map = new HashMap<>();
// queue to hold tree node with level
Queue<Pair> q = new LinkedList<Pair>();
// Root node is at level 1
q.add(new Pair(root, 1));
Pair p;
// Level Order Traversal of tree
while (!q.isEmpty()) {
p = q.peek();
q.remove();
// Create a key for each level
// in the map
if (!map.containsKey(p.i))
map.put(p.i, 0);
// If current node is a leaf node
if (p.n.left == null && p.n.right == null)
{
// Adding value in the map
// corresponding to its level
map.put(p.i, map.get(p.i) + p.n.data);
}
if (p.n.left != null)
q.add(new Pair(p.n.left, p.i + 1));
if (p.n.right != null)
q.add(new Pair(p.n.right, p.i + 1));
}
// Print the sum at each level
for (Map.Entry mapElement : map.entrySet()) {
int value = ((int)mapElement.getValue());
System.out.println(value);
}
}
// Driver Code
public static void main(String args[])
{
Node root = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.right = new Node(8);
root.left.right.right = new Node(9);
root.right.right.left = new Node(10);
root.right.right.right = new Node(11);
root.left.left.right.right = new Node(12);
printLevelSum(root);
}
}
// This code is contributed by vineetsharma36.
Python3
# Python3 program for the above approach
class newNode:
# Construct to create a new node
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Function to print the sum of leaf nodes
# at each horizontal level
def printLevelSum(root):
if (not root):
print("No nodes present")
return
# Dictionary to hold sum at each level
dict = {}
# queue to hold tree node with level
q = []
# Root node is at level 1
q.append([root, 1])
p = []
# Level order Traversal of Tree
while (len(q)):
p=q[0]
q.pop(0)
# Create a key for each level
# in the dictionary
if (p[1] not in dict.keys()):
dict[p[1]] = 0
# If current node is a leaf node
if (not p[0].left and not p[0].right):
# Adding value in the dictionary
# corresponding to its level
dict[p[1]] = p[0].data + dict.get(p[1])
if (p[0].left):
q.append([p[0].left, p[1] + 1])
if (p[0].right):
q.append([p[0].right, p[1] + 1])
# Print the sum at each level
for sum in dict.values():
print(sum)
# Driver Code
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.left = newNode(6)
root.right.right = newNode(7)
root.left.left.right = newNode(8)
root.left.right.right = newNode(9)
root.right.right.left = newNode(10)
root.right.right.right = newNode(11)
root.left.left.right.right = newNode(12)
printLevelSum(root)
# This code is contributed by vineetsharma36.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class Print_Level_Sum_Btree {
/* A tree node structure */
public class Node {
public int data;
public Node left;
public Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}
// User defined class Pair to hold
// the node and its level
public class Pair{
public Node n;
public int i;
public Pair(Node n, int i){
this.n = n;
this.i = i;
}
}
// Function to print the sum of leaf nodes
// at each horizontal level
static void printLevelSum(Node root)
{
if (root == null)
{
Console.WriteLine("No nodes present");
return;
}
// hashmap to hold sum at each level
Dictionary<int, int> map = new Dictionary<int,int>();
// queue to hold tree node with level
Queue<Pair> q = new Queue<Pair>();
// Root node is at level 1
q.Enqueue(new Pair(root, 1));
Pair p;
// Level Order Traversal of tree
while (q.Count!=0) {
p = q.Peek();
q.Dequeue();
// Create a key for each level
// in the map
if (!map.ContainsKey(p.i))
map.Add(p.i, 0);
// If current node is a leaf node
if (p.n.left == null && p.n.right == null)
{
// Adding value in the map
// corresponding to its level
map[p.i]= map[p.i] + p.n.data;
}
if (p.n.left != null)
q.Enqueue(new Pair(p.n.left, p.i + 1));
if (p.n.right != null)
q.Enqueue(new Pair(p.n.right, p.i + 1));
}
// Print the sum at each level
foreach(KeyValuePair<int, int> entry in map){
int value = (entry.Value);
Console.WriteLine(value);
}
}
// Driver Code
public static void Main(String []args)
{
Node root = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.right = new Node(8);
root.left.right.right = new Node(9);
root.right.right.left = new Node(10);
root.right.right.right = new Node(11);
root.left.left.right.right = new Node(12);
printLevelSum(root);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// Javascript program for the above approach
// Tree node structure
class Node {
constructor(data) {
this.data = data;
this.left = this.right = null;
}
}
// Function to print the sum of leaf nodes
// at each horizontal level
function printLevelSum(root) {
if (root == null) {
document.write("No nodes present\n");
return;
}
// Map to hold sum at each level
let mp = new Map();
// Queue to hold tree node with level
let q = [];
// Root node is at level 1
q.push([root, 1]);
let p = [];
// Level Order Traversal of tree
while (q.length) {
p = q[q.length - 1];
q.pop();
// Create a key for each level
// in the map
if (!mp.has(p[1])) {
mp.set(p[1], 0);
}
// If current node is a leaf node
if (p[0].left == null && p[0].right == null) {
// Adding value in the map
// corresponding to its level
mp.set(p[1], mp.get(p[1]) + p[0].data);
}
if (p[0].left) q.push([p[0].left, p[1] + 1]);
if (p[0].right) q.push([p[0].right, p[1] + 1]);
}
// Print the sum at each level
for (let i of mp) {
document.write(i[1] + "<bR>");
}
}
// Driver Code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.right = new Node(8);
root.left.right.right = new Node(9);
root.right.right.left = new Node(10);
root.right.right.right = new Node(11);
root.left.left.right.right = new Node(12);
printLevelSum(root);
</script>
Producción
0 0 6 30 12
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vineetsharma36 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA