Suma de Nodes a la máxima profundidad de un árbol binario | conjunto 2

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++ 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 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 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#  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 */

<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>

22

Complejidad temporal : O(N) donde N es el número de vértices en el árbol binario.
Espacio Auxiliar : O(N).