Dado un Node raíz de un árbol, encuentre la suma de todos los Nodes hoja que se encuentran a la máxima profundidad desde el Node raíz.
Ejemplo:
1
/ \
2 3
/ \ / \
4 5 6 7
Input : root(of above tree)
Output : 22
Explanation:
Nodes at maximum depth are 4, 5, 6, 7.
So, the sum of these nodes = 22
Enfoque: Existe un enfoque recursivo para este problema. Esto también se puede resolver utilizando el mapa y el recorrido de orden de nivel. La idea es hacer un recorrido utilizando una cola y realizar un seguimiento del nivel actual. Se ha utilizado un mapa para almacenar la suma de Nodes en el nivel actual. Una vez que se visitan todos los Nodes y se realiza el recorrido, el último elemento del mapa contendrá la suma en la profundidad máxima del árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to calculate the sum of
// nodes at the maximum depth of a binary tree
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
node *left, *right;
} * temp;
node* newNode(int data)
{
temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to return the sum
int SumAtMaxLevel(node* root)
{
// Map to store level wise sum.
map<int, int> mp;
// Queue for performing Level Order Traversal.
// First entry is the node and
// second entry is the level of this node.
queue<pair<node*, int> > q;
// Root has level 0.
q.push({ root, 0 });
while (!q.empty()) {
// Get the node from front of Queue.
pair<node*, int> temp = q.front();
q.pop();
// Get the depth of current node.
int depth = temp.second;
// Add the value of this node in map.
mp[depth] += (temp.first)->data;
// Push children of this node,
// with increasing the depth.
if (temp.first->left)
q.push({ temp.first->left, depth + 1 });
if (temp.first->right)
q.push({ temp.first->right, depth + 1 });
}
map<int, int>::iterator it;
// Get the max depth from map.
it = mp.end();
// last element
it--;
// return the max Depth sum.
return it->second;
}
// Driver Code
int main()
{
node* 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);
cout << SumAtMaxLevel(root) << endl;
return 0;
}
Java
// Java program to calculate
// the sum of nodes at the
// maximum depth of a binary tree
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
class GFG{
static class Node
{
int data;
Node left, right;
public Node(int data)
{
this.data = data;
this.left = this.right =
null;
}
}
static class Pair
{
Node node;
int data;
public Pair(Node node,
int data)
{
this.node = node;
this.data = data;
}
}
// Function to return the sum
static int SumAtMaxLevel(Node root)
{
// Map to store level wise sum.
HashMap<Integer,
Integer> mp = new HashMap<>();
// Queue for performing Level
// Order Traversal. First entry
// is the node and second entry
// is the level of this node.
Queue<Pair> q = new LinkedList<>();
// Root has level 0.
q.add(new Pair(root, 0));
while (!q.isEmpty())
{
// Get the node from
// front of Queue.
Pair temp = q.poll();
// Get the depth of
// current node.
int depth = temp.data;
// Add the value of this
// node in map.
if (!mp.containsKey(depth))
mp.put(depth, 0);
mp.put(depth, mp.get(depth) +
temp.node.data);
// Push children of this node,
// with increasing the depth.
if (temp.node.left != null)
q.add(new Pair(temp.node.left,
depth + 1));
if (temp.node.right != null)
q.add(new Pair(temp.node.right,
depth + 1));
}
Object[] values = mp.values().toArray();
return (int) values[values.length - 1];
}
// Driver Code
public static void main(String[] args)
{
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);
System.out.println(SumAtMaxLevel(root));
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to calculate the
# sum of nodes at the maximum depth
# of a binary tree
# Helper function that allocates a
# new node with the given data and
# None left and right pointers.
class newNode:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to return the sum
def SumAtMaxLevel(root):
# Map to store level wise sum.
mp = {}
# Queue for performing Level Order
# Traversal. First entry is the node
# and second entry is the level of
# this node.
q = []
# Root has level 0.
q.append([root, 0])
while (len(q)):
# Get the node from front
# of Queue.
temp = q[0]
q.pop(0)
# Get the depth of current node.
depth = temp[1]
# Add the value of this node in map.
if depth not in mp:
mp[depth] = 0
mp[depth] += (temp[0]).data
# append children of this node,
# with increasing the depth.
if (temp[0].left) :
q.append([temp[0].left,
depth + 1])
if (temp[0].right) :
q.append([temp[0].right,
depth + 1])
# return the max Depth sum.
return list(mp.values())[-1]
# Driver Code
if __name__ == '__main__':
# Let us construct the Tree
# shown in the above figure
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)
print(SumAtMaxLevel(root))
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to calculate
// the sum of nodes at the
// maximum depth of a binary tree
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
class GFG{
class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
this.left = this.right =
null;
}
}
class Pair
{
public Node node;
public int data;
public Pair(Node node,
int data)
{
this.node = node;
this.data = data;
}
}
// Function to return the sum
static int SumAtMaxLevel(Node root)
{
// Map to store level wise sum.
Dictionary<int,int> mp = new Dictionary<int,int>();
// Queue for performing Level
// Order Traversal. First entry
// is the node and second entry
// is the level of this node.
Queue q = new Queue();
// Root has level 0.
q.Enqueue(new Pair(root, 0));
while (q.Count != 0)
{
// Get the node from
// front of Queue.
Pair temp = (Pair)q.Dequeue();
// Get the depth of
// current node.
int depth = temp.data;
// Add the value of this
// node in map.
if (!mp.ContainsKey(depth))
mp[depth]= 0;
mp[depth] = mp[depth]+temp.node.data;
// Push children of this node,
// with increasing the depth.
if (temp.node.left != null)
q.Enqueue(new Pair(temp.node.left,
depth + 1));
if (temp.node.right != null)
q.Enqueue(new Pair(temp.node.right,
depth + 1));
}
return mp.Values.Last();
}
// Driver Code
public static void Main(string[] args)
{
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);
Console.WriteLine(SumAtMaxLevel(root));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to calculate
// the sum of nodes at the maximum
// depth of a binary tree
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class Pair
{
constructor(node, data)
{
this.node = node;
this.data = data;
}
}
// Function to return the sum
function SumAtMaxLevel(root)
{
// Map to store level wise sum.
var mp = new Map();
// Queue for performing Level
// Order Traversal. First entry
// is the node and second entry
// is the level of this node.
var q = [];
// Root has level 0.
q.push(new Pair(root, 0));
while (q.length != 0)
{
// Get the node from
// front of Queue.
var temp = q.pop();
// Get the depth of
// current node.
var depth = temp.data;
// Add the value of this
// node in map.
if (!mp.has(depth))
mp.set(depth, 0);
mp.set(depth, mp.get(depth) +
temp.node.data)
// Push children of this node,
// with increasing the depth.
if (temp.node.left != null)
q.push(new Pair(temp.node.left,
depth + 1));
if (temp.node.right != null)
q.push(new Pair(temp.node.right,
depth + 1));
}
return [...mp][mp.size - 1][1];
}
// Driver Code
var 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);
document.write(SumAtMaxLevel(root));
// This code is contributed by famously
</script>
Producción:
22
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA