Maximice la suma de la ruta desde la raíz hasta un Node hoja en el árbol N-ario

Dado un árbol genérico que consta de N Nodes, la tarea es encontrar la suma máxima de la ruta desde la raíz hasta el Node hoja .

Ejemplos:

Aporte:

Salida: 12
Explicación: La suma de la ruta a cada hoja desde la raíz es:
Para el Node 4: 1 -> 2 -> 4 = 7
Para el Node 5: 1 -> 2 -> 5 = 8
Para el Node 6: 1 -> 3 -> 6 = 10
Para el Node 7: 1 -> 3 -> 7 = 11
Para el Node 8: 1 -> 3 -> 8 = 12 (máximo)

La suma máxima de rutas es 12, es decir, desde la raíz 1 hasta la hoja 8.

Enfoque: el problema dado se puede resolver realizando el recorrido DFS en el árbol dado . La idea es realizar el DFS Traversal desde el Node raíz del árbol genérico dado manteniendo el seguimiento de la suma de los valores de los Nodes en cada ruta y, si se produce algún Node hoja, maximizar el valor de la suma actual de la ruta obtenida en un variable, digamos maxSum .

Después de realizar DFS Traversal , imprima el valor de maxSum como la ruta de suma máxima resultante.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node in the tree
struct Node {
    int val;
    vector<Node*> child;
};
 
// Utility function to create a
// new node in the tree
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->val = key;
    return temp;
}
 
// Recursive function to calculate the
// maximum sum in a path using DFS
void DFS(Node* root, int sum, int& ans)
{
    // If current node is a leaf node
    if (root->child.size() == 0) {
        ans = max(ans, sum);
        return;
    }
 
    // Traversing all children of
    // the current node
    for (int i = 0;
         i < root->child.size(); i++) {
 
        // Recursive call for all
        // the children nodes
        DFS(root->child[i],
            sum + root->child[i]->val, ans);
    }
}
 
// Driver Code
int main()
{
    // Given Generic Tree
    Node* root = newNode(1);
    (root->child).push_back(newNode(2));
    (root->child).push_back(newNode(3));
    (root->child[0]->child).push_back(newNode(4));
    (root->child[1]->child).push_back(newNode(6));
    (root->child[0]->child).push_back(newNode(5));
    (root->child[1])->child.push_back(newNode(7));
    (root->child[1]->child).push_back(newNode(8));
 
    // Stores the maximum sum of a path
    int maxSumPath = 0;
 
    // Function Call
    DFS(root, root->val, maxSumPath);
 
    cout << maxSumPath;
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class Main
{
   
    // Stores the maximum sum of a path
    static int maxSumPath = 0;
     
    // Structure of a node in the tree
    static class Node {
         
        public int val;
        public Vector<Node> child;
         
        public Node(int key)
        {
            val = key;
            child = new Vector<Node>();
        }
    }
     
    // Utility function to create a
    // new node in the tree
    static Node newNode(int key)
    {
        Node temp = new Node(key);
        return temp;
    }
       
    // Recursive function to calculate the
    // maximum sum in a path using DFS
    static void DFS(Node root, int sum)
    {
        // If current node is a leaf node
        if (root.child.size() == 0) {
            maxSumPath = Math.max(maxSumPath, sum);
            return;
        }
       
        // Traversing all children of
        // the current node
        for (int i = 0; i < root.child.size(); i++) {
       
            // Recursive call for all
            // the children nodes
            DFS(root.child.get(i), sum + root.child.get(i).val);
        }
    }
     
    public static void main(String[] args) {
        // Given Generic Tree
        Node root = newNode(1);
        (root.child).add(newNode(2));
        (root.child).add(newNode(3));
        (root.child.get(0).child).add(newNode(4));
        (root.child.get(1).child).add(newNode(6));
        (root.child.get(0).child).add(newNode(5));
        (root.child.get(1)).child.add(newNode(7));
        (root.child.get(1).child).add(newNode(8));
         
        // Function Call
        DFS(root, root.val);
         
        System.out.print(maxSumPath);
    }
}
 
// This code is contributed by divyeshrabadiya07.

# Python3 program for the above approach
 
# Stores the maximum sum of a path
maxSumPath = 0
 
# Structure of a node in the tree
class Node:
    def __init__(self, key):
        self.val = key
        self.child = []
 
# Utility function to create a
# new node in the tree
def newNode(key):
    temp = Node(key)
    return temp
 
# Recursive function to calculate the
# maximum sum in a path using DFS
def DFS(root, Sum):
    global maxSumPath
    # If current node is a leaf node
    if (len(root.child) == 0):
        maxSumPath = max(maxSumPath, Sum)
        return
 
    # Traversing all children of
    # the current node
    for i in range(len(root.child)):
        # Recursive call for all
        # the children nodes
        DFS(root.child[i], Sum + root.child[i].val)
 
# Given Generic Tree
root = newNode(1)
(root.child).append(newNode(2))
(root.child).append(newNode(3))
(root.child[0].child).append(newNode(4))
(root.child[1].child).append(newNode(6))
(root.child[0].child).append(newNode(5))
(root.child[1]).child.append(newNode(7))
(root.child[1].child).append(newNode(8))
 
# Function Call
DFS(root, root.val)
 
print(maxSumPath)
 
# This code is contributed by rameshtravel07.

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
     
    // Stores the maximum sum of a path
    static int maxSumPath = 0;
     
    // Structure of a node in the tree
    class Node {
        
        public int val;
        public List<Node> child;
        
        public Node(int key)
        {
            val = key;
            child = new List<Node>();
        }
    }
     
    // Utility function to create a
    // new node in the tree
    static Node newNode(int key)
    {
        Node temp = new Node(key);
        return temp;
    }
      
    // Recursive function to calculate the
    // maximum sum in a path using DFS
    static void DFS(Node root, int sum)
    {
        // If current node is a leaf node
        if (root.child.Count == 0) {
            maxSumPath = Math.Max(maxSumPath, sum);
            return;
        }
      
        // Traversing all children of
        // the current node
        for (int i = 0;
             i < root.child.Count; i++) {
      
            // Recursive call for all
            // the children nodes
            DFS(root.child[i],
                sum + root.child[i].val);
        }
    }
     
  static void Main() {
    // Given Generic Tree
    Node root = newNode(1);
    (root.child).Add(newNode(2));
    (root.child).Add(newNode(3));
    (root.child[0].child).Add(newNode(4));
    (root.child[1].child).Add(newNode(6));
    (root.child[0].child).Add(newNode(5));
    (root.child[1]).child.Add(newNode(7));
    (root.child[1].child).Add(newNode(8));
    
    // Function Call
    DFS(root, root.val);
    
    Console.Write(maxSumPath);
  }
}
 
// This code is contributed by mukesh07.

<script>
    // Javascript program for the above approach
     
    // Stores the maximum sum of a path
    let maxSumPath = 0;
     
    // Structure of a node in the tree
    class Node
    {
        constructor(key) {
           this.child = [];
           this.val = key;
        }
    }
     
    // Utility function to create a
    // new node in the tree
    function newNode(key)
    {
        let temp = new Node(key);
        return temp;
    }
 
    // Recursive function to calculate the
    // maximum sum in a path using DFS
    function DFS(root, sum)
    {
        // If current node is a leaf node
        if (root.child.length == 0) {
            maxSumPath = Math.max(maxSumPath, sum);
            return;
        }
 
        // Traversing all children of
        // the current node
        for (let i = 0; i < root.child.length; i++) {
 
            // Recursive call for all
            // the children nodes
            DFS(root.child[i],
                sum + root.child[i].val);
        }
    }
     
    // Given Generic Tree
    let root = newNode(1);
    (root.child).push(newNode(2));
    (root.child).push(newNode(3));
    (root.child[0].child).push(newNode(4));
    (root.child[1].child).push(newNode(6));
    (root.child[0].child).push(newNode(5));
    (root.child[1]).child.push(newNode(7));
    (root.child[1].child).push(newNode(8));
   
    // Function Call
    DFS(root, root.val);
   
    document.write(maxSumPath);
     
    // This code is contributed by decode2207.
</script>

12

Complejidad temporal: O(N)
Espacio auxiliar: O(1)