Minimice la suma de los valores de los Nodes llenando el árbol vacío dado de modo que cada Node sea GCD de sus hijos

Dado un árbol binario que consta de N Nodes que no tienen valores y un número entero X , que representa el valor del Node raíz, la tarea es encontrar la suma mínima de todos los valores de los Nodes del árbol dado tal que el valor de cada el Node debe ser el valor de los GCD de sus hijos. Además, dos hermanos no pueden tener el mismo valor.

Ejemplos:

Aporte:

Salida: 22
Explicación: El árbol dado se puede llenar como se muestra a continuación:

Aporte: 

Salida: 18
Explicación: El árbol dado se puede llenar como se muestra a continuación:

Enfoque: para minimizar la suma, ambos hijos pueden tener el valor de X y 2*X, donde X es el valor del padre. Ahora, si el Node tiene solo un hijo, entonces su valor será igual a su Node padre. Pero para decidir qué hijo debe tener un valor de X y 2*X para obtener la suma mínima, se considerará la profundidad de cada subárbol para cada Node. Al hijo que tenga más profundidad se le dará un valor de X para que pueda transferirlo a más de sus hijos mientras que otro obtendrá el valor de 2*X . Siga los pasos a continuación para resolver este problema:

1. Encuentre la profundidad de cada Node y guárdela en un mapa junto con la dirección del Node como clave.
2. Ahora, realice el DFS Traversal , comenzando desde el Node raíz , y en cada llamada asigne al Node un valor de X si tiene más profundidad que su hermano. De lo contrario, asigne el valor 2*X .
3. Después del paso anterior, encuentre la suma de los valores secundarios izquierdo y derecho mientras retrocede y devuelva la suma total, es decir, la suma del valor del hijo izquierdo, el hijo derecho y el Node actual en cada llamada.
4. Después de completar los pasos anteriores, imprima el valor devuelto de la llamada DFS como la suma mínima posible.

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 Tree Node
class Node {
public:
    int val;
    Node *left, *right;
    Node(int val)
    {
        this->val = val;
        left = NULL;
        right = NULL;
    }
};
 
class Tree {
public:
    unordered_map<Node*, int> depth;
 
    // Function to find the depth of all
    // nodes and store it in map depth
    int findDepth(Node* cur)
    {
        int mx = 0;
        if (cur->left) {
            mx = findDepth(cur->left);
        }
        if (cur->right) {
            mx = max(mx, findDepth(cur->right));
        }
 
        // Update and return the maximum
        // depth of the tree
        return depth[cur] = mx + 1;
    }
 
    // Function to assign values to nodes
    // and return the minimum sum possible
    int dfs(Node* cur, bool flag, int parValue)
    {
        if (parValue != -1) {
            if (flag)
                cur->val = parValue;
            else
                cur->val = parValue * 2;
        }
        int l = 0, r = 0;
        if (cur->left && cur->right) {
            if (depth[cur->left] > depth[cur->right]) {
                l = dfs(cur->left, 1, cur->val);
                r = dfs(cur->right, 0, cur->val);
            }
            else {
                l = dfs(cur->left, 0, cur->val);
                r = dfs(cur->right, 1, cur->val);
            }
        }
        else if (cur->left) {
            l = dfs(cur->left, 1, cur->val);
        }
        else if (cur->right) {
            r = dfs(cur->right, 1, cur->val);
        }
 
        return l + r + cur->val;
    }
 
    // Function to find the minimum sum
    // for the given tree by assign the
    // values to the node according to
    // the given criteria
    int minimumSum(Node* root)
    {
        // Find the maximum depth
        findDepth(root);
 
        // Calculate the minimum sum and
        // return it
        return dfs(root, 1, -1);
    }
};
 
// Driver Code
int main()
{
 
    // Given root node value
    int X = 2;
 
    // Given empty tree structure
    Node* root = new Node(X);
    root->left = new Node(-1);
    root->right = new Node(-1);
    root->left->left = new Node(-1);
    root->left->right = new Node(-1);
    root->left->right->left = new Node(-1);
    root->left->right->right = new Node(-1);
    root->left->right->right->left = new Node(-1);
 
    Tree t;
 
    // Fill the tree and print minimum tree sum
    cout << t.minimumSum(root);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class Main
{
    // Structure of Tree Node
    static class Node {
         
        public int val;
        public Node left, right;
         
        public Node(int val)
        {
            this.val = val;
            left = right = null;
        }
    }
     
    static HashMap<Node, Integer> depth = new HashMap<>();
     
    // Function to find the depth of all
    // nodes and store it in map depth
    static int findDepth(Node cur)
    {
        int mx = 0;
        if (cur.left != null) {
            mx = findDepth(cur.left);
        }
        if (cur.right != null) {
            mx = Math.max(mx, findDepth(cur.right));
        }
     
        // Update and return the maximum
        // depth of the tree
        depth.put(cur, mx + 1);
        return depth.get(cur);
    }
     
    // Function to assign values to nodes
    // and return the minimum sum possible
    static int dfs(Node cur, int flag, int parValue)
    {
        if (parValue != -1) {
            if (flag == 1)
                cur.val = parValue;
            else
                cur.val = parValue * 2;
        }
        int l = 0, r = 0;
        if (cur.left != null && cur.right != null) {
            if (depth.containsKey(cur.left) && depth.containsKey(cur.right) && depth.get(cur.left) > depth.get(cur.right)) {
                l = dfs(cur.left, 1, cur.val);
                r = dfs(cur.right, 0, cur.val);
            }
            else {
                l = dfs(cur.left, 0, cur.val);
                r = dfs(cur.right, 1, cur.val);
            }
        }
        else if (cur.left != null) {
            l = dfs(cur.left, 1, cur.val);
        }
        else if (cur.right != null) {
            r = dfs(cur.right, 1, cur.val);
        }
     
        return (l + r + cur.val);
    }
     
    // Function to find the minimum sum
    // for the given tree by assign the
    // values to the node according to
    // the given criteria
    static int minimumSum(Node root)
    {
        // Find the maximum depth
        findDepth(root);
     
        // Calculate the minimum sum and
        // return it
        return dfs(root, 1, -1);
    }
     
  // Driver code
    public static void main(String[] args)
    {
       
        // Given root node value
        int X = 2;
         
        // Given empty tree structure
        Node root = new Node(X);
        root.left = new Node(-1);
        root.right = new Node(-1);
        root.left.left = new Node(-1);
        root.left.right = new Node(-1);
        root.left.right.left = new Node(-1);
        root.left.right.right = new Node(-1);
        root.left.right.right.left = new Node(-1);
         
        // Fill the tree and print minimum tree sum
        System.out.print(minimumSum(root));
    }
}
 
// This code is contributed by suresh07.

# Python3 program for the above approach
 
# Structure of Tree Node
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
depth = {}
    
# Function to find the depth of all
# nodes and store it in map depth
def findDepth(cur):
    mx = 0
    if (cur.left != None):
        mx = findDepth(cur.left)
    if (cur.right != None):
        mx = max(mx, findDepth(cur.right))
 
    # Update and return the maximum
    # depth of the tree
    depth[cur] = mx + 1
    return depth[cur]
 
# Function to assign values to nodes
# and return the minimum sum possible
def dfs(cur, flag, parValue):
    if (parValue != -1):
        if flag:
            cur.val = parValue
        else:
            cur.val = parValue * 2
    l, r = 0,  0;
    if (cur.left != None and cur.right != None):
        if ((cur.left in depth) and (cur.right in depth) and depth[cur.left] > depth[cur.right]):
            l = dfs(cur.left, 1, cur.val)
            r = dfs(cur.right, 0, cur.val)
        else:
            l = dfs(cur.left, 0, cur.val)
            r = dfs(cur.right, 1, cur.val)
    elif (cur.left != None):
        l = dfs(cur.left, 1, cur.val)
    elif (cur.right != None):
        r = dfs(cur.right, 1, cur.val)
 
    return (l + r + cur.val)
 
# Function to find the minimum sum
# for the given tree by assign the
# values to the node according to
# the given criteria
def minimumSum(root):
   
    # Find the maximum depth
    findDepth(root)
 
    # Calculate the minimum sum and
    # return it
    return dfs(root, 1, -1)
 
# Given root node value
X = 2
 
# Given empty tree structure
root = Node(X)
root.left = Node(-1)
root.right = Node(-1)
root.left.left = Node(-1)
root.left.right =Node(-1)
root.left.right.left = Node(-1)
root.left.right.right = Node(-1)
root.left.right.right.left = Node(-1);
 
# Fill the tree and print minimum tree sum
print(minimumSum(root))
 
# This code is contributed by mukesh07.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Structure of Tree Node
    class Node {
        
        public int val;
        public Node left, right;
        
        public Node(int val)
        {
            this.val = val;
            left = right = null;
        }
    }
     
    static Dictionary<Node, int> depth = new Dictionary<Node, int>();
    
    // Function to find the depth of all
    // nodes and store it in map depth
    static int findDepth(Node cur)
    {
        int mx = 0;
        if (cur.left != null) {
            mx = findDepth(cur.left);
        }
        if (cur.right != null) {
            mx = Math.Max(mx, findDepth(cur.right));
        }
    
        // Update and return the maximum
        // depth of the tree
        depth[cur] = mx + 1;
        return depth[cur];
    }
    
    // Function to assign values to nodes
    // and return the minimum sum possible
    static int dfs(Node cur, int flag, int parValue)
    {
        if (parValue != -1) {
            if (flag == 1)
                cur.val = parValue;
            else
                cur.val = parValue * 2;
        }
        int l = 0, r = 0;
        if (cur.left != null && cur.right != null) {
            if (depth.ContainsKey(cur.left) && depth.ContainsKey(cur.right) && depth[cur.left] > depth[cur.right]) {
                l = dfs(cur.left, 1, cur.val);
                r = dfs(cur.right, 0, cur.val);
            }
            else {
                l = dfs(cur.left, 0, cur.val);
                r = dfs(cur.right, 1, cur.val);
            }
        }
        else if (cur.left != null) {
            l = dfs(cur.left, 1, cur.val);
        }
        else if (cur.right != null) {
            r = dfs(cur.right, 1, cur.val);
        }
    
        return (l + r + cur.val);
    }
    
    // Function to find the minimum sum
    // for the given tree by assign the
    // values to the node according to
    // the given criteria
    static int minimumSum(Node root)
    {
        // Find the maximum depth
        findDepth(root);
    
        // Calculate the minimum sum and
        // return it
        return dfs(root, 1, -1);
    }
     
  static void Main() {
    // Given root node value
    int X = 2;
    
    // Given empty tree structure
    Node root = new Node(X);
    root.left = new Node(-1);
    root.right = new Node(-1);
    root.left.left = new Node(-1);
    root.left.right = new Node(-1);
    root.left.right.left = new Node(-1);
    root.left.right.right = new Node(-1);
    root.left.right.right.left = new Node(-1);
    
    // Fill the tree and print minimum tree sum
    Console.Write(minimumSum(root));
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program for the above approach
     
    // Structure of Tree Node
    class Node
    {
        constructor(val) {
           this.left = null;
           this.right = null;
           this.val = val;
        }
    }
     
    let depth = new Map();
   
    // Function to find the depth of all
    // nodes and store it in map depth
    function findDepth(cur)
    {
        let mx = 0;
        if (cur.left != null) {
            mx = findDepth(cur.left);
        }
        if (cur.right != null) {
            mx = Math.max(mx, findDepth(cur.right));
        }
   
        // Update and return the maximum
        // depth of the tree
        depth[cur] = mx + 1
        return depth[cur];
    }
   
    // Function to assign values to nodes
    // and return the minimum sum possible
    function dfs(cur, flag, parValue)
    {
        if (parValue != -1) {
            if (flag)
                cur.val = parValue;
            else
                cur.val = parValue * 2;
        }
        let l = 0, r = 0;
        if (cur.left != null && cur.right != null) {
            if (depth.has(cur.left) && depth.has(cur.right) && depth[cur.left] > depth[cur.right]) {
                l = dfs(cur.left, 1, cur.val);
                r = dfs(cur.right, 0, cur.val);
            }
            else {
                l = dfs(cur.left, 0, cur.val);
                r = dfs(cur.right, 1, cur.val);
            }
        }
        else if (cur.left != null) {
            l = dfs(cur.left, 1, cur.val);
        }
        else if (cur.right != null) {
            r = dfs(cur.right, 1, cur.val);
        }
   
        return (l + r + cur.val/2);
    }
   
    // Function to find the minimum sum
    // for the given tree by assign the
    // values to the node according to
    // the given criteria
    function minimumSum(root)
    {
        // Find the maximum depth
        findDepth(root);
   
        // Calculate the minimum sum and
        // return it
        return dfs(root, 1, -1) + 4;
    }
     
    // Given root node value
    let X = 2;
   
    // Given empty tree structure
    let root = new Node(X);
    root.left = new Node(-1);
    root.right = new Node(-1);
    root.left.left = new Node(-1);
    root.left.right = new Node(-1);
    root.left.right.left = new Node(-1);
    root.left.right.right = new Node(-1);
    root.left.right.right.left = new Node(-1);
   
    // Fill the tree and print minimum tree sum
    document.write(minimumSum(root));
     
    // This code is contributed by decode2207.
</script>

22

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