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, sum of these nodes = 22
En el artículo anterior discutimos una solución recursiva que primero encuentra el nivel máximo y luego encuentra la suma de todos los Nodes presentes en ese nivel.
En este artículo veremos una solución recursiva sin encontrar la altura ni la profundidad. La idea es que mientras atraviesa los Nodes compare el nivel del Node con max_level (Nivel máximo hasta el Node actual). Si el nivel actual supera el nivel máximo, actualice max_level como nivel actual. Si el nivel máximo y el nivel actual son iguales, agregue los datos raíz a la suma actual; de lo contrario, si el nivel es menor que max_level, no haga nada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find sum of nodes at maximum
// Depth of the Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Variables to store sum and
// maximum level
int sum = 0, max_level = INT_MIN;
// Binary Tree Node
struct Node {
int data;
Node* left;
Node* right;
};
// Utility function to create and
// return a new Binary Tree Node
Node* createNode(int val)
{
Node* node = new Node;
node->data = val;
node->left = NULL;
node->right = NULL;
return node;
}
// Function to find the sum of the node which
// are present at the maximum depth
void sumOfNodesAtMaxDepth(Node* root, int level)
{
if (root == NULL)
return;
// If the current level exceeds the
// maximum level, update the max_level
// as current level.
if (level > max_level) {
sum = root->data;
max_level = level;
}
// If the max level and current level
// are same, add the root data to
// current sum.
else if (level == max_level) {
sum = sum + root->data;
}
// Traverse the left and right subtrees
sumOfNodesAtMaxDepth(root->left, level + 1);
sumOfNodesAtMaxDepth(root->right, level + 1);
}
// Driver Code
int main()
{
Node* root;
root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
cout << sum;
return 0;
}
Java
// Java Program to find sum of nodes at maximum
// Depth of the Binary Tree
class GfG
{
// Variables to store sum and
// maximum level
static int sum = 0,
max_level = Integer.MIN_VALUE;
// Binary Tree Node
static class Node
{
int data;
Node left;
Node right;
}
// Utility function to create and
// return a new Binary Tree Node
static Node createNode(int val)
{
Node node = new Node();
node.data = val;
node.left = null;
node.right = null;
return node;
}
// Function to find the sum of
// the node which are present
// at the maximum depth
static void sumOfNodesAtMaxDepth(Node root,
int level)
{
if (root == null)
return;
// If the current level exceeds the
// maximum level, update the max_level
// as current level.
if (level > max_level)
{
sum = root.data;
max_level = level;
}
// If the max level and current level
// are same, add the root data to
// current sum.
else if (level == max_level)
{
sum = sum + root.data;
}
// Traverse the left and right subtrees
sumOfNodesAtMaxDepth(root.left, level + 1);
sumOfNodesAtMaxDepth(root.right, level + 1);
}
// Driver Code
public static void main(String[] args)
{
Node root = null;
root = createNode(1);
root.left = createNode(2);
root.right = createNode(3);
root.left.left = createNode(4);
root.left.right = createNode(5);
root.right.left = createNode(6);
root.right.right = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
System.out.println(sum);
}
}
// This code is contributed by
// Prerna Saini.
Python3
# Python3 Program to find sum of nodes at maximum # Depth of the Binary Tree # Variables to store sum and # maximum level sum = [0] max_level = [-(2**32)] # Binary tree node class createNode: def __init__(self, data): self.data = data self.left = None self.right = None # Function to find the sum of the node which # are present at the maximum depth def sumOfNodesAtMaxDepth(root, level): if (root == None): return # If the current level exceeds the # maximum level, update the max_level # as current level. if (level > max_level[0]): sum[0] = root.data max_level[0] = level # If the max level and current level #are same, add the root data to # current sum. elif (level == max_level[0]): sum[0] = sum[0] + root.data # Traverse the left and right subtrees sumOfNodesAtMaxDepth(root.left, level + 1) sumOfNodesAtMaxDepth(root.right, level + 1) # Driver Code root = createNode(1) root.left = createNode(2) root.right = createNode(3) root.left.left = createNode(4) root.left.right = createNode(5) root.right.left = createNode(6) root.right.right = createNode(7) sumOfNodesAtMaxDepth(root, 0) print(sum[0]) # This code is contributed by SHUBHAMSINGH10
C#
// C# Program to find sum of nodes at maximum
// Depth of the Binary Tree
using System;
public class GfG
{
// Variables to store sum and
// maximum level
static int sum = 0,
max_level = int.MinValue;
// Binary Tree Node
class Node
{
public int data;
public Node left;
public Node right;
}
// Utility function to create and
// return a new Binary Tree Node
static Node createNode(int val)
{
Node node = new Node();
node.data = val;
node.left = null;
node.right = null;
return node;
}
// Function to find the sum of
// the node which are present
// at the maximum depth
static void sumOfNodesAtMaxDepth(Node root,
int level)
{
if (root == null)
return;
// If the current level exceeds the
// maximum level, update the max_level
// as current level.
if (level > max_level)
{
sum = root.data;
max_level = level;
}
// If the max level and current level
// are same, add the root data to
// current sum.
else if (level == max_level)
{
sum = sum + root.data;
}
// Traverse the left and right subtrees
sumOfNodesAtMaxDepth(root.left, level + 1);
sumOfNodesAtMaxDepth(root.right, level + 1);
}
// Driver Code
public static void Main()
{
Node root = null;
root = createNode(1);
root.left = createNode(2);
root.right = createNode(3);
root.left.left = createNode(4);
root.left.right = createNode(5);
root.right.left = createNode(6);
root.right.right = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
Console.WriteLine(sum);
}
}
/* This code is contributed PrinciRaj1992 */
Javascript
<script>
// JavaScript Program to find sum of nodes at maximum
// Depth of the Binary Tree
// Variables to store sum and
// maximum level
let sum = 0;
let max_level = Number.MIN_VALUE;
// Binary Tree Node
class Node
{
constructor(val) {
this.left = null;
this.right = null;
this.data = val;
}
}
// Utility function to create and
// return a new Binary Tree Node
function createNode(val)
{
let node = new Node(val);
return node;
}
// Function to find the sum of
// the node which are present
// at the maximum depth
function sumOfNodesAtMaxDepth(root, level)
{
if (root == null)
return;
// If the current level exceeds the
// maximum level, update the max_level
// as current level.
if (level > max_level)
{
sum = root.data;
max_level = level;
}
// If the max level and current level
// are same, add the root data to
// current sum.
else if (level == max_level)
{
sum = sum + root.data;
}
// Traverse the left and right subtrees
sumOfNodesAtMaxDepth(root.left, level + 1);
sumOfNodesAtMaxDepth(root.right, level + 1);
}
let root = null;
root = createNode(1);
root.left = createNode(2);
root.right = createNode(3);
root.left.left = createNode(4);
root.left.right = createNode(5);
root.right.left = createNode(6);
root.right.right = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
document.write(sum);
</script>
Producción:
22
Complejidad temporal : O(N) donde N es el número de vértices en el árbol binario.
Espacio Auxiliar : O(N).
Publicación traducida automáticamente
Artículo escrito por Ashwin Loganathan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA