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:
C++
// Code to find the sum of the nodes
// which are present at the maximum depth.
#include <bits/stdc++.h>
using namespace std;
int sum = 0, max_level = INT_MIN;
struct Node
{
int d;
Node *l;
Node *r;
};
// Function to return a new node
Node* createNode(int d)
{
Node *node;
node = new Node;
node->d = d;
node->l = NULL;
node->r = NULL;
return node;
}
// Function to find the sum of the node
// which are present at the maximum depth.
// While traversing the nodes compare the level
// of the node with max_level
// (Maximum level till the current node).
// If the current level exceeds the maximum level,
// update the max_level as current level.
// If the max level and current level are same,
// add the root data to current sum.
void sumOfNodesAtMaxDepth(Node *ro,int level)
{
if(ro == NULL)
return;
if(level > max_level)
{
sum = ro -> d;
max_level = level;
}
else if(level == max_level)
{
sum = sum + ro -> d;
}
sumOfNodesAtMaxDepth(ro -> l, level + 1);
sumOfNodesAtMaxDepth(ro -> r, level + 1);
}
// Driver Code
int main()
{
Node *root;
root = createNode(1);
root->l = createNode(2);
root->r = createNode(3);
root->l->l = createNode(4);
root->l->r = createNode(5);
root->r->l = createNode(6);
root->r->r = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
cout << sum;
return 0;
}
Java
// Java code to find the sum of the nodes
// which are present at the maximum depth.
class GFG
{
static int sum = 0, max_level = Integer.MIN_VALUE;
static class Node
{
int d;
Node l;
Node r;
};
// Function to return a new node
static Node createNode(int d)
{
Node node;
node = new Node();
node.d = d;
node.l = null;
node.r = null;
return node;
}
// Function to find the sum of the node
// which are present at the maximum depth.
// While traversing the nodes compare the level
// of the node with max_level
// (Maximum level till the current node).
// If the current level exceeds the maximum level,
// update the max_level as current level.
// If the max level and current level are same,
// add the root data to current sum.
static void sumOfNodesAtMaxDepth(Node ro,int level)
{
if(ro == null)
return;
if(level > max_level)
{
sum = ro . d;
max_level = level;
}
else if(level == max_level)
{
sum = sum + ro . d;
}
sumOfNodesAtMaxDepth(ro . l, level + 1);
sumOfNodesAtMaxDepth(ro . r, level + 1);
}
// Driver Code
public static void main(String[] args)
{
Node root;
root = createNode(1);
root.l = createNode(2);
root.r = createNode(3);
root.l.l = createNode(4);
root.l.r = createNode(5);
root.r.l = createNode(6);
root.r.r = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
System.out.println(sum);
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python3 code to find the sum of the nodes # which are present at the maximum depth. sum = [0] max_level = [-(2**32)] # Binary tree node class createNode: def __init__(self, data): self.d = data self.l = None self.r = None # Function to find the sum of the node # which are present at the maximum depth. # While traversing the nodes compare the level # of the node with max_level # (Maximum level till the current node). # If the current level exceeds the maximum level, # update the max_level as current level. # If the max level and current level are same, # add the root data to current sum. def sumOfNodesAtMaxDepth(ro, level): if(ro == None): return if(level > max_level[0]): sum[0] = ro . d max_level[0] = level elif(level == max_level[0]): sum[0] = sum[0] + ro . d sumOfNodesAtMaxDepth(ro . l, level + 1) sumOfNodesAtMaxDepth(ro . r, level + 1) # Driver Code root = createNode(1) root.l = createNode(2) root.r = createNode(3) root.l.l = createNode(4) root.l.r = createNode(5) root.r.l = createNode(6) root.r.r = createNode(7) sumOfNodesAtMaxDepth(root, 0) print(sum[0]) # This code is contributed by SHUBHAMSINGH10
C#
// C# code to find the sum of the nodes
// which are present at the maximum depth.
using System;
class GFG
{
static int sum = 0, max_level = int.MinValue;
public class Node
{
public int d;
public Node l;
public Node r;
};
// Function to return a new node
static Node createNode(int d)
{
Node node;
node = new Node();
node.d = d;
node.l = null;
node.r = null;
return node;
}
// Function to find the sum of the node
// which are present at the maximum depth.
// While traversing the nodes compare the level
// of the node with max_level
// (Maximum level till the current node).
// If the current level exceeds the maximum level,
// update the max_level as current level.
// If the max level and current level are same,
// add the root data to current sum.
static void sumOfNodesAtMaxDepth(Node ro,int level)
{
if(ro == null)
return;
if(level > max_level)
{
sum = ro . d;
max_level = level;
}
else if(level == max_level)
{
sum = sum + ro . d;
}
sumOfNodesAtMaxDepth(ro . l, level + 1);
sumOfNodesAtMaxDepth(ro . r, level + 1);
}
// Driver Code
public static void Main(String[] args)
{
Node root;
root = createNode(1);
root.l = createNode(2);
root.r = createNode(3);
root.l.l = createNode(4);
root.l.r = createNode(5);
root.r.l = createNode(6);
root.r.r = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
Console.WriteLine(sum);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript code to find the sum of the nodes
// which are present at the maximum depth.
var sum = 0, max_level = -1000000000;
class Node
{
constructor()
{
this.d = 0;
this.l = null;
this.r = null;
}
};
// Function to return a new node
function createNode(d)
{
var node;
node = new Node();
node.d = d;
node.l = null;
node.r = null;
return node;
}
// Function to find the sum of the node
// which are present at the maximum depth.
// While traversing the nodes compare the level
// of the node with max_level
// (Maximum level till the current node).
// If the current level exceeds the maximum level,
// update the max_level as current level.
// If the max level and current level are same,
// add the root data to current sum.
function sumOfNodesAtMaxDepth(ro, level)
{
if (ro == null)
return;
if (level > max_level)
{
sum = ro . d;
max_level = level;
}
else if (level == max_level)
{
sum = sum + ro . d;
}
sumOfNodesAtMaxDepth(ro.l, level + 1);
sumOfNodesAtMaxDepth(ro.r, level + 1);
}
// Driver Code
var root;
root = createNode(1);
root.l = createNode(2);
root.r = createNode(3);
root.l.l = createNode(4);
root.l.r = createNode(5);
root.r.l = createNode(6);
root.r.r = createNode(7);
sumOfNodesAtMaxDepth(root, 0);
document.write(sum);
// This code is contributed by rrrtnx
</script>
C++
// C++ code for sum of nodes
// at maximum depth
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node* left, *right;
// Constructor
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// function to find the sum of nodes at
// maximum depth arguments are node and
// max, where max is to match the depth
// of node at every call to node, if
// max will be equal to 1, means
// we are at deepest node.
int sumMaxLevelRec(Node* node, int max)
{
// base case
if (node == NULL)
return 0;
// max == 1 to track the node
// at deepest level
if (max == 1)
return node->data;
// recursive call to left and right nodes
return sumMaxLevelRec(node->left, max - 1) +
sumMaxLevelRec(node->right, max - 1);
}
// maxDepth function to find the
// max depth of the tree
int maxDepth(Node* node)
{
// base case
if (node == NULL)
return 0;
// either leftDepth of rightDepth is
// greater add 1 to include height
// of node at which call is
return 1 + max(maxDepth(node->left),
maxDepth(node->right));
}
int sumMaxLevel(Node* root)
{
// call to function to calculate
// max depth
int MaxDepth = maxDepth(root);
return sumMaxLevelRec(root, MaxDepth);
}
// Driver code
int main()
{
/* 1
/ \
2 3
/ \ / \
4 5 6 7 */
// Constructing tree
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);
// call to calculate required sum
cout<<(sumMaxLevel(root))<<endl;
}
// This code is contributed by Arnab Kundu
Java
// Java code for sum of nodes
// at maximum depth
import java.util.*;
class Node {
int data;
Node left, right;
// Constructor
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class GfG {
// function to find the sum of nodes at
// maximum depth arguments are node and
// max, where max is to match the depth
// of node at every call to node, if
// max will be equal to 1, means
// we are at deepest node.
public static int sumMaxLevelRec(Node node,
int max)
{
// base case
if (node == null)
return 0;
// max == 1 to track the node
// at deepest level
if (max == 1)
return node.data;
// recursive call to left and right nodes
return sumMaxLevelRec(node.left, max - 1) +
sumMaxLevelRec(node.right, max - 1);
}
public static int sumMaxLevel(Node root) {
// call to function to calculate
// max depth
int MaxDepth = maxDepth(root);
return sumMaxLevelRec(root, MaxDepth);
}
// maxDepth function to find the
// max depth of the tree
public static int maxDepth(Node node)
{
// base case
if (node == null)
return 0;
// either leftDepth of rightDepth is
// greater add 1 to include height
// of node at which call is
return 1 + Math.max(maxDepth(node.left),
maxDepth(node.right));
}
// Driver code
public static void main(String[] args)
{
/* 1
/ \
2 3
/ \ / \
4 5 6 7 */
// Constructing tree
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);
// call to calculate required sum
System.out.println(sumMaxLevel(root));
}
}
Python3
# Python3 code for sum of nodes at maximum depth class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to find the sum of nodes at maximum depth # arguments are node and max, where Max is to match # the depth of node at every call to node, if Max # will be equal to 1, means we are at deepest node. def sumMaxLevelRec(node, Max): # base case if node == None: return 0 # Max == 1 to track the node at deepest level if Max == 1: return node.data # recursive call to left and right nodes return (sumMaxLevelRec(node.left, Max - 1) + sumMaxLevelRec(node.right, Max - 1)) def sumMaxLevel(root): # call to function to calculate max depth MaxDepth = maxDepth(root) return sumMaxLevelRec(root, MaxDepth) # maxDepth function to find # the max depth of the tree def maxDepth(node): # base case if node == None: return 0 # Either leftDepth of rightDepth is # greater add 1 to include height # of node at which call is return 1 + max(maxDepth(node.left), maxDepth(node.right)) # Driver code if __name__ == "__main__": # Constructing tree 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) # call to calculate required sum print(sumMaxLevel(root)) # This code is contributed by Rituraj Jain
C#
using System;
// C# code for sum of nodes
// at maximum depth
public class Node
{
public int data;
public Node left, right;
// Constructor
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class GfG
{
// function to find the sum of nodes at
// maximum depth arguments are node and
// max, where max is to match the depth
// of node at every call to node, if
// max will be equal to 1, means
// we are at deepest node.
public static int sumMaxLevelRec(Node node, int max)
{
// base case
if (node == null)
{
return 0;
}
// max == 1 to track the node
// at deepest level
if (max == 1)
{
return node.data;
}
// recursive call to left and right nodes
return sumMaxLevelRec(node.left, max - 1)
+ sumMaxLevelRec(node.right, max - 1);
}
public static int sumMaxLevel(Node root)
{
// call to function to calculate
// max depth
int MaxDepth = maxDepth(root);
return sumMaxLevelRec(root, MaxDepth);
}
// maxDepth function to find the
// max depth of the tree
public static int maxDepth(Node node)
{
// base case
if (node == null)
{
return 0;
}
// either leftDepth of rightDepth is
// greater add 1 to include height
// of node at which call is
return 1 + Math.Max(maxDepth(node.left),
maxDepth(node.right));
}
// Driver code
public static void Main(string[] args)
{
/* 1
/ \
2 3
/ \ / \
4 5 6 7 */
// Constructing tree
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);
// call to calculate required sum
Console.WriteLine(sumMaxLevel(root));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript code for sum of nodes at maximum depth
// Structure of a tree node.
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// function to find the sum of nodes at
// maximum depth arguments are node and
// max, where max is to match the depth
// of node at every call to node, if
// max will be equal to 1, means
// we are at deepest node.
function sumMaxLevelRec(node, max)
{
// base case
if (node == null)
return 0;
// max == 1 to track the node
// at deepest level
if (max == 1)
return node.data;
// recursive call to left and right nodes
return sumMaxLevelRec(node.left, max - 1) +
sumMaxLevelRec(node.right, max - 1);
}
function sumMaxLevel(root) {
// call to function to calculate
// max depth
let MaxDepth = maxDepth(root);
return sumMaxLevelRec(root, MaxDepth);
}
// maxDepth function to find the
// max depth of the tree
function maxDepth(node)
{
// base case
if (node == null)
return 0;
// either leftDepth of rightDepth is
// greater add 1 to include height
// of node at which call is
return 1 + Math.max(maxDepth(node.left),
maxDepth(node.right));
}
/* 1
/ \
2 3
/ \ / \
4 5 6 7 */
// Constructing tree
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);
// call to calculate required sum
document.write(sumMaxLevel(root));
// This code is contributed by divyesh072019.
</script>
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
};
// Function to return a new node
TreeNode *createNode(int d)
{
TreeNode *node;
node = new TreeNode();
node->val = d;
node->left = NULL;
node->right = NULL;
return node;
}
// Iterative function to find the sum of the deepest
// nodes.
int deepestLeavesSum(TreeNode *root)
{
// if the root is NULL then return 0
if (root == NULL)
{
return 0;
}
// Initialize an empty queue.
queue<TreeNode *> qu;
// push the root of the tree into the queue
qu.push(root);
// initialize sum of current level to 0
int sumOfCurrLevel = 0;
// loop until the queue is not empty
while (!qu.empty())
{
int size = qu.size();
sumOfCurrLevel = 0;
while (size-- > 0)
{
TreeNode *head = qu.front();
qu.pop();
sumOfCurrLevel += head->val;
// if the left child of the head is not NULL
if (head->left != NULL)
{
//push the child into the queue
qu.push(head->left);
}
// if the right child is not NULL
if (head->right != NULL)
{
// push the child into the queue
qu.push(head->right);
}
}
}
return sumOfCurrLevel;
}
// Driver code
int main()
{
TreeNode *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);
cout << (deepestLeavesSum(root));
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java code to print the sum of leaves present at maximum
// depth of a binary tree
import java.util.*;
class GFG {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
};
// Function to return a new node
static TreeNode createNode(int d)
{
TreeNode node;
node = new TreeNode();
node.val = d;
node.left = null;
node.right = null;
return node;
}
// Iterative function to find the sum of the deepest
// nodes.
public static int deepestLeavesSum(TreeNode root)
{
// if the root is null then return 0
if (root== null) {
return 0;
}
// Initialize an empty queue.
Queue<TreeNode> qu= new LinkedList<>();
// push the root of the tree into the queue
qu.offer(root);
// initialize sum of current level to 0
int sumOfCurrLevel= 0;
// loop until the queue is not empty
while (!qu.isEmpty()) {
int size = qu.size();
sumOfCurrLevel = 0;
while (size-- > 0) {
TreeNode head = qu.poll();
sumOfCurrLevel += head.val;
// if the left child of the head is not null
if (head.left!= null) {
//push the child into the queue
qu.offer(head.left);
}
// if the right child is not null
if (head.right!= null) {
// push the child into the queue
qu.offer(head.right);
}
}
}
return sumOfCurrLevel;
}
public static void main(String[] args)
{
TreeNode 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);
System.out.println(deepestLeavesSum(root));
}
}
// this code is contributed by Rohan Raj
Python3
# Python code to print the sum # of leaves present at maximum # depth of a binary tree class TreeNode: def __init__(self): self.val = 0 self.left = None self.right = None def createNode(d): node = TreeNode() node.val = d node.left = None node.right = None return node # Iterative function to find the sum of the deepest # nodes. def deepestLeavesSum(root): # if the root is None then return 0 if (root== None): return 0 # Initialize an empty queue. qu= [] # append the root of the tree into the queue qu.append(root) # initialize sum of current level to 0 sumOfCurrLevel= 0 # loop until the queue is not empty while (len(qu) != 0): size = len(qu) sumOfCurrLevel = 0 while (size): head = qu[0] qu = qu[1:] sumOfCurrLevel += head.val # if the left child of the head is not None if (head.left!= None): # append the child into the queue qu.append(head.left) # if the right child is not None if (head.right!= None): # append the child into the queue qu.append(head.right) size -= 1 return sumOfCurrLevel 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) print(deepestLeavesSum(root)) # This code is contributed by shinjanpatra
C#
// C# code to print the sum of leaves present at maximum
// depth of a binary tree
using System;
using System.Collections.Generic;
public class GFG {
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
};
// Function to return a new node
static TreeNode createNode(int d)
{
TreeNode node;
node = new TreeNode();
node.val = d;
node.left = null;
node.right = null;
return node;
}
// Iterative function to find the sum of the deepest
// nodes.
public static int deepestLeavesSum(TreeNode root)
{
// if the root is null then return 0
if (root == null)
{
return 0;
}
// Initialize an empty queue.
Queue<TreeNode> qu= new Queue<TreeNode>();
// push the root of the tree into the queue
qu.Enqueue(root);
// initialize sum of current level to 0
int sumOfCurrLevel= 0;
// loop until the queue is not empty
while (qu.Count != 0)
{
int size = qu.Count;
sumOfCurrLevel = 0;
while (size-- > 0)
{
TreeNode head = qu.Dequeue();
sumOfCurrLevel += head.val;
// if the left child of the head is not null
if (head.left!= null)
{
//push the child into the queue
qu.Enqueue(head.left);
}
// if the right child is not null
if (head.right!= null)
{
// push the child into the queue
qu.Enqueue(head.right);
}
}
}
return sumOfCurrLevel;
}
public static void Main(String[] args)
{
TreeNode 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);
Console.WriteLine(deepestLeavesSum(root));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript code to print the sum
// of leaves present at maximum
// depth of a binary tree
class TreeNode
{
constructor()
{
this.val=0;
this.left=this.right=null;
}
}
function createNode(d)
{
let node;
node = new TreeNode();
node.val = d;
node.left = null;
node.right = null;
return node;
}
// Iterative function to find the sum of the deepest
// nodes.
function deepestLeavesSum(root)
{
// if the root is null then return 0
if (root== null) {
return 0;
}
// Initialize an empty queue.
let qu= [];
// push the root of the tree into the queue
qu.push(root);
// initialize sum of current level to 0
let sumOfCurrLevel= 0;
// loop until the queue is not empty
while (qu.length!=0) {
let size = qu.length;
sumOfCurrLevel = 0;
while (size-- > 0) {
let head = qu.shift();
sumOfCurrLevel += head.val;
// if the left child of the head is not null
if (head.left!= null) {
//push the child into the queue
qu.push(head.left);
}
// if the right child is not null
if (head.right!= null) {
// push the child into the queue
qu.push(head.right);
}
}
}
return sumOfCurrLevel;
}
let 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);
document.write(deepestLeavesSum(root));
// This code is contributed by avanitrachhadiya2155
</script>
Publicación traducida automáticamente
Artículo escrito por Dhiman Mayank y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA