Producto máximo de cualquier ruta en el árbol binario dado

Dado un árbol binario de N Nodes, la tarea es encontrar el producto máximo de los elementos de cualquier camino en el árbol binario. 

Nota: un camino comienza desde la raíz y termina en cualquier hoja del árbol.

Ejemplos:

Entrada:
           4
        / \
     2 8
  / \ / \
2 1 3 4

Salida: 128
Explicación: la ruta en el árbol dado es {4, 8, 4}, lo que da la puntuación máxima de 4 x 8 x 4 = 128.

Entrada:
    10
  / \
7 5
         \
          1

Salida: 70 
Explicación: La ruta {10, 7} da una puntuación de 70 que es la máxima posible.

Enfoque: la idea para resolver el problema es usar el recorrido DFS de un árbol usando recursividad .

Para cada Node, encuentre recursivamente el producto máximo del subárbol izquierdo y el subárbol derecho de ese Node y devuelva el producto de ese valor con los datos del Node.

Siga los pasos mencionados a continuación para resolver el problema

• Como condición base. Si la raíz es NULL, simplemente devuelva 1.
• Llame a la función recursiva para los subárboles izquierdo y derecho para obtener el producto máximo de ambos subárboles.
• Devuelve el valor del Node actual multiplicado por el producto máximo del subárbol izquierdo y derecho como la respuesta de la recursividad actual.

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

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a tree Node
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) { this->data = val; }
};
 
// Utility function to create a new Tree Node
long long findMaxScore(Node* root)
{
    // Base Condition
    if (root == 0)
        return 1;
 
    // Mmax product path = root->data
    // multiplied by max of
    // max_product_path of left subtree
    // and max_product_path
    // of right subtree
    return root->data
           * max(findMaxScore(root->left),
                 findMaxScore(root->right));
}
 
// Driver Code
int main()
{
    Node* root = new Node(4);
    root->left = new Node(2);
    root->right = new Node(8);
    root->left->left = new Node(3);
    root->left->right = new Node(1);
    root->right->left = new Node(3);
    root->right->right = new Node(4);
 
    // Function call
    cout << findMaxScore(root) << endl;
    return 0;
}

// Java code for the above approach:
import java.util.*;
class GFG
{
 
  // Structure of a tree Node
  public static class Node {
    int data;
    Node left;
    Node right;
    Node(int val) { this.data = val; }
  }
 
  // Utility function to create a new Tree Node
  public static long findMaxScore(Node root)
  {
    // Base Condition
    if (root == null)
      return 1;
 
    // Mmax product path = root.data
    // multiplied by max of
    // max_product_path of left subtree
    // and max_product_path
    // of right subtree
    return root.data
      * Math.max(findMaxScore(root.left),
                 findMaxScore(root.right));
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    Node root = new Node(4);
    root.left = new Node(2);
    root.right = new Node(8);
    root.left.left = new Node(3);
    root.left.right = new Node(1);
    root.right.left = new Node(3);
    root.right.right = new Node(4);
 
    // Function call
    System.out.println(findMaxScore(root));
  }
}
 
// This code is contributed by Taranpreet

# Python code for the above approach
 
# Structure of a tree Node
class Node:
    def __init__(self,d):
        self.data = d
        self.left = None
        self.right = None
 
# Utility function to create a new Tree Node
def findMaxScore(root):
 
    # Base Condition
    if (root == None):
        return 1
 
    # Mmax product path = root->data
    # multiplied by max of
    # max_product_path of left subtree
    # and max_product_path
    # of right subtree
    return root.data * max(findMaxScore(root.left),findMaxScore(root.right))
 
# Driver Code
root = Node(4)
root.left = Node(2)
root.right = Node(8)
root.left.left = Node(3)
root.left.right = Node(1)
root.right.left = Node(3)
root.right.right = Node(4)
 
# Function call
print(findMaxScore(root))
 
# This code is contributed by shinjanpatra

// C# code to implement the approach
using System;
 
class GFG
{
 
  // Structure of a tree Node
  public class Node {
    public int data;
    public Node left;
    public Node right;
    public Node(int val) { this.data = val; }
  }
 
  // Utility function to create a new Tree Node
  public static long findMaxScore(Node root)
  {
    // Base Condition
    if (root == null)
      return 1;
 
    // Mmax product path = root.data
    // multiplied by max of
    // max_product_path of left subtree
    // and max_product_path
    // of right subtree
    return root.data
      * Math.Max(findMaxScore(root.left),
                 findMaxScore(root.right));
  }
 
// Driver Code
public static void Main()
{
    Node root = new Node(4);
    root.left = new Node(2);
    root.right = new Node(8);
    root.left.left = new Node(3);
    root.left.right = new Node(1);
    root.right.left = new Node(3);
    root.right.right = new Node(4);
 
    // Function call
    Console.WriteLine(findMaxScore(root));
}
}
 
// This code is contributed by jana_sayantan.

<script>
       // JavaScript code for the above approach
 
       // Structure of a tree Node
       class Node
       {
           constructor(d)
           {
               this.data = d;
               this.left = null;
               this.right = null;
           }
       };
 
       // Utility function to create a new Tree Node
       function findMaxScore(root)
       {
        
           // Base Condition
           if (root == null)
               return 1;
 
           // Mmax product path = root->data
           // multiplied by max of
           // max_product_path of left subtree
           // and max_product_path
           // of right subtree
           return root.data
               * Math.max(findMaxScore(root.left),
                   findMaxScore(root.right));
       }
 
       // Driver Code
       let root = new Node(4);
       root.left = new Node(2);
       root.right = new Node(8);
       root.left.left = new Node(3);
       root.left.right = new Node(1);
       root.right.left = new Node(3);
       root.right.right = new Node(4);
 
       // Function call
       document.write(findMaxScore(root) + '<br>');
 
     // This code is contributed by Potta Lokesh
   </script>

128

Complejidad temporal: O(N).
Espacio Auxiliar: O( Altura del árbol)