Dado un árbol binario que contiene n Nodes. La tarea es encontrar la suma de todos los Nodes hoja presentes en el nivel máximo.
Ejemplos:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
Output: 17
Leaf nodes 8 and 9 are at maximum level.
Their sum = (8 + 9) = 17.
Input:
5
/ \
8 13
/
4
Output: 4
Enfoque: Realice un recorrido de orden de nivel iterativo utilizando la cola y encuentre la suma de los Nodes en cada nivel y, si no hay elementos secundarios para cada Node en el nivel actual, marque este nivel como el nivel máximo. La suma de todos los Nodes hoja en el nivel máximo será la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#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 return the sum of the
// leaf nodes at maximum level
int sumOfLeafNodesAtMaxLevel(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 leafSum = 0;
bool f = 0;
// Push root node in the queue 'q'
q.push(root);
while (true) {
// Count number of nodes in the
// current level
int nc = q.size();
// If the queue is empty, it means that the
// last processed level was the maximum level
if (nc == 0)
return leafSum;
// Initialize leafSum for current level
leafSum = 0;
// 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'
leafSum += top->data;
}
else {
// If top's left and right child
// exist then push them to 'q'
if (top->left)
q.push(top->left);
if (top->right)
q.push(top->right);
}
}
}
}
// Driver code
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 << sumOfLeafNodesAtMaxLevel(root);
return 0;
}
Java
// Java implementation of the approach
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 return the sum of the
// leaf nodes at maximum level
static int sumOfLeafNodesAtMaxLevel(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 leafSum = 0;
boolean f = false;
// Push root node in the queue 'q'
q.add(root);
while (true) {
// Count number of nodes in the
// current level
int nc = q.size();
// If the queue is empty, it means that the
// last processed level was the maximum level
if (nc == 0)
return leafSum;
// Initialize leafSum for current level
leafSum = 0;
// 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'
leafSum += top.data;
}
else {
// If top's left and right child
// exist then push them to 'q'
if (top.left != null)
q.add(top.left);
if (top.right != null)
q.add(top.right);
}
}
}
}
// 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.print(sumOfLeafNodesAtMaxLevel(root));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python implementation of the approach # Structure of a node of binary tree class Node: def __init__(self): self.data = 0 self.left = None self.right = None # Function to get a new node def getNode(data): # Allocate space newNode = Node() # Put in the data newNode.data = data newNode.left = newNode.right = None return newNode # Function to return the sum of the # leaf nodes at maximum level def sumOfLeafNodesAtMaxLevel(root): # If tree is empty if (root == None): return 0 # If there is only one node if (root.left == None and root.right == None): return root.data # Queue used for level order traversal q = [] leafSum = 0 # append root node in the queue 'q' q.append(root) while (True): # Count number of nodes in the # current level nc = len(q) # If the queue is empty, it means that the # last processed level was the maximum level if (nc == 0): return leafSum # Initialize leafSum for current level leafSum = 0 # Traverse the current level nodes while (nc > 0): # Get front element from 'q' top = q[0] q.pop(0) # If it is a leaf node if (top.left == None and top.right == None): # Accumulate data to 'sum' leafSum += top.data else: # If top's left and right child # exist then append them to 'q' if (top.left != None): q.append(top.left) if (top.right != None): q.append(top.right) nc -= 1 # Driver code # Binary tree creation 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) print(sumOfLeafNodesAtMaxLevel(root)) # This code is contributed by shinjanpatra
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
// Structure of a node of binary tree
public 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 return the sum of the
// leaf nodes at maximum level
static int sumOfLeafNodesAtMaxLevel(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 leafSum = 0;
// Push root node in the queue 'q'
q.Enqueue(root);
while (true) {
// Count number of nodes in the
// current level
int nc = q.Count;
// If the queue is empty, it means that the
// last processed level was the maximum level
if (nc == 0)
return leafSum;
// Initialize leafSum for current level
leafSum = 0;
// 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'
leafSum += top.data;
}
else {
// If top's left and right child
// exist then push them to 'q'
if (top.left != null)
q.Enqueue(top.left);
if (top.right != null)
q.Enqueue(top.right);
}
}
}
}
// 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.Write(sumOfLeafNodesAtMaxLevel(root));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Structure of a node of binary tree
class Node {
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Function to get a new node
function getNode(data)
{
// Allocate space
var newNode = new Node();
// Put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// Function to return the sum of the
// leaf nodes at maximum level
function sumOfLeafNodesAtMaxLevel(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
var q = [];
var leafSum = 0;
// Push root node in the queue 'q'
q.push(root);
while (true) {
// Count number of nodes in the
// current level
var nc = q.length;
// If the queue is empty, it means that the
// last processed level was the maximum level
if (nc == 0)
return leafSum;
// Initialize leafSum for current level
leafSum = 0;
// Traverse the current level nodes
while (nc-- > 0) {
// Get front element from 'q'
var top = q[0];
q.shift();
// If it is a leaf node
if (top.left == null && top.right == null) {
// Accumulate data to 'sum'
leafSum += top.data;
}
else {
// If top's left and right child
// exist then push them to 'q'
if (top.left != null)
q.push(top.left);
if (top.right != null)
q.push(top.right);
}
}
}
}
// Driver code
// Binary tree creation
var 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(sumOfLeafNodesAtMaxLevel(root));
</script>
Producción:
17
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
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