Dado un árbol binario , la tarea es encontrar el valor máximo de GCD desde cualquier ruta desde el Node raíz hasta el Node hoja .
Ejemplos:
Entrada: A continuación se muestra el árbol dado:
Salida: 3
Explicación:
Camino 1: 15->3->5 = mcd(15, 3, 15) =3
Camino 2: 15->3->1 =mcd(15, 3, 1) = 1
Camino 3: 15->7->31=mcd(15, 7, 31)= 1
Camino 4: 15->7->9 = mcd(15, 7, 9) =1, de estos 3 es el máximo.Entrada: A continuación se muestra el árbol dado:
Salida: 1
Enfoque: La idea es recorrer todos los caminos desde el Node raíz hasta el Node hoja y calcular el GCD de todos los Nodes que ocurrieron en ese camino. A continuación se muestran los pasos:
- Realice un recorrido de preorden en el árbol binario dado .
- Iterar sobre todas las rutas y realizar un seguimiento de todos los valores de ruta en una array.
- Siempre que encuentre un valor de hoja, busque el GCD de todos los valores en una array.
- Actualice el GCD al valor máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Initialise to update the maximum // gcd value from all the path int maxm = 0; // Node structure struct Node { int val; // Left & right child of the node Node *left, *right; // Initialize constructor Node(int x) { val = x; left = NULL; right = NULL; } }; // Function to find gcd of a and b int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // function to find the gcd of a path int find_gcd(vector<int> arr) { if (arr.size() == 1) return arr[0]; int g = arr[0]; for (int i = 1; i < arr.size(); i++) { g = gcd(g, arr[i]); } return g; } // Function to find the maximum value // of gcd from root to leaf // in a Binary tree void maxm_gcd(Node* root, vector<int> ans) { // Check if root is not null if (!root) return; if (root->left == NULL and root->right == NULL) { ans.push_back(root->val); // Find the maximum gcd of // path value and store in // global maxm variable maxm = max(find_gcd(ans), maxm); return; } // Traverse left of binary tree ans.push_back(root->val); maxm_gcd(root->left, ans); // Traverse right of the binary tree maxm_gcd(root->right, ans); } // Driver Code int main() { // Given Tree Node* root = new Node(15); root->left = new Node(3); root->right = new Node(7); root->left->left = new Node(15); root->left->right = new Node(1); root->right->left = new Node(31); root->right->right = new Node(9); // Function Call maxm_gcd(root, {}); // Print the maximum AND value cout << maxm << endl; return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Initialise to update the maximum // gcd value from all the path static int maxm = 0; // Node structure static class Node { int val; // Left & right child of the node Node left, right; // Initialize constructor Node(int x) { val = x; left = null; right = null; } }; // Function to find gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the gcd of a path static int find_gcd(Vector<Integer> arr) { if (arr.size() == 1) return arr.get(0); int g = arr.get(0); for(int i = 1; i < arr.size(); i++) { g = gcd(g, arr.get(1)); } return g; } // Function to find the maximum value // of gcd from root to leaf // in a Binary tree static void maxm_gcd(Node root, Vector<Integer> ans) { // Check if root is not null if (root == null) return; if (root.left == null && root.right == null) { ans.add(root.val); // Find the maximum gcd of // path value and store in // global maxm variable maxm = Math.max(find_gcd(ans), maxm); return; } // Traverse left of binary tree ans.add(root.val); maxm_gcd(root.left, ans); // Traverse right of the binary tree maxm_gcd(root.right, ans); } // Driver Code public static void main(String[] args) { // Given Tree Node root = new Node(15); root.left = new Node(3); root.right = new Node(7); root.left.left = new Node(15); root.left.right = new Node(1); root.right.left = new Node(31); root.right.right = new Node(9); // Function call maxm_gcd(root, new Vector<>()); // Print the maximum AND value System.out.print(maxm + "\n"); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation of # the above approach # Initialise to update the maximum # gcd value from all the path global maxm maxm = 0 # Node structure class Node: # Initialize constructor def __init__(self, x): self.val = x self.left = None self.right = None # Function to find gcd of a and b def gcd(a, b): if(b == 0): return a return gcd(b, a % b) # Function to find the gcd of a path def find_gcd(arr): if(len(arr) == 1): return arr[0] g = arr[0] for i in range(1, len(arr)): g = gcd(g, arr[i]) return g # Function to find the maximum value # of gcd from root to leaf # in a Binary tree def maxm_gcd(root, ans): global maxm # Check if root is not null if(not root): return if(root.left == None and root.right == None): ans.append(root.val) # Find the maximum gcd of # path value and store in # global maxm variable maxm = max(find_gcd(ans), maxm) return # Traverse left of binary tree ans.append(root.val) maxm_gcd(root.left, ans) # Traverse right of the binary tree maxm_gcd(root.right, ans) # Driver Code if __name__ == '__main__': # Given Tree root = Node(15) root.left = Node(3) root.right = Node(7) root.left.left = Node(15) root.left.right = Node(1) root.right.left = Node(31) root.right.right = Node(9) # Function call maxm_gcd(root, []) # Print the maximum AND value print(maxm) # This code is contributed by Shivam Singh
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Initialise to update the maximum // gcd value from all the path static int maxm = 0; // Node structure class Node { public int val; // Left & right child of the node public Node left, right; // Initialize constructor public Node(int x) { val = x; left = null; right = null; } }; // Function to find gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the gcd of a path static int find_gcd(List<int> arr) { if (arr.Count == 1) return arr[0]; int g = arr[0]; for(int i = 1; i < arr.Count; i++) { g = gcd(g, arr[1]); } return g; } // Function to find the maximum value // of gcd from root to leaf // in a Binary tree static void maxm_gcd(Node root, List<int> ans) { // Check if root is not null if (root == null) return; if (root.left == null && root.right == null) { ans.Add(root.val); // Find the maximum gcd of // path value and store in // global maxm variable maxm = Math.Max(find_gcd(ans), maxm); return; } // Traverse left of binary tree ans.Add(root.val); maxm_gcd(root.left, ans); // Traverse right of the binary tree maxm_gcd(root.right, ans); } // Driver Code public static void Main(String[] args) { // Given Tree Node root = new Node(15); root.left = new Node(3); root.right = new Node(7); root.left.left = new Node(15); root.left.right = new Node(1); root.right.left = new Node(31); root.right.right = new Node(9); // Function call maxm_gcd(root, new List<int>()); // Print the maximum AND value Console.Write(maxm + "\n"); } } // This code is contributed by sapnasingh4991
Javascript
<script> // JavaScript program for the above approach // Initialise to update the maximum // gcd value from all the path let maxm = 0; // Node structure class Node { // Initialize constructor constructor(x) { this.val = x; this.left = null; this.right = null; } } var root; // Function to find gcd of a and b function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the gcd of a path function find_gcd(arr) { if (arr.length == 1) return arr[0]; let g = arr[0]; for(let i = 1; i < arr.length; i++) { g = gcd(g, arr[1]); } return g; } // Function to find the maximum value // of gcd from root to leaf // in a Binary tree function maxm_gcd(root, ans) { // Check if root is not null if (root == null) return; if (root.left == null && root.right == null) { ans.push(root.val); // Find the maximum gcd of // path value and store in // global maxm variable maxm = Math.max(find_gcd(ans), maxm); return; } // Traverse left of binary tree ans.push(root.val); maxm_gcd(root.left, ans); // Traverse right of the binary tree maxm_gcd(root.right, ans); } // Driver Code // Given Tree root = new Node(15); root.left = new Node(3); root.right = new Node(7); root.left.left = new Node(15); root.left.right = new Node(1); root.right.left = new Node(31); root.right.right = new Node(9); // Function call let arr = []; maxm_gcd(root, arr); // Print the maximum AND value document.write(maxm); // This code is contributed by Dharanendra L V. </script>
3
Complejidad del Tiempo : O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA